25.03.18 코딩테스트 대비

BOJ 2096. 내려가기

---

2096번: 내려가기

 

 

 

내 코드

import sys

input = sys.stdin.readline

n = int(input())

dp1 = [0, 0, 0]
dp2 = [0, 0, 0]

for _ in range(n):
    nums = (list(map(int, input().split())))
    dp1[0], dp1[1], dp1[2] = min(dp1[0], dp1[1]) + nums[0], min(dp1) + nums[1], min(dp1[1], dp1[2]) + nums[2]
    dp2[0], dp2[1], dp2[2] = max(dp2[0], dp2[1]) + nums[0], max(dp2) + nums[1], max(dp2[1], dp2[2]) + nums[2]

print(max(dp2), min(dp1))

처음 문제를 봤을 때 bfs나 dfs로 풀어야할까 했는데 이렇게 풀면 무조건 시간초과가 걸릴 것 같아 dp로 접근하여 문제를 해결했다.

 

최솟값과 최댓값을 구해야하기 때문에 dp1, dp2를 만들었고, nums 값들을 입력받을 때마다 dp1은 다음과 같은 점화식으로 업데이트 해 나갔다.

 

dp1[0] = min(dp1[0], dp1[1]) + nums[0]

dp1[1] = min(dp1) + nums[1]

dp1[2] = min(dp1[1], dp1[2]) + nums[2]

 

dp2는 위 점화식에서 min을 max로 바꿔주면 된다

 

dp2[0] = max(dp2[0], dp2[1]) + nums[0]

dp2[1] = max(dp2) + nums[1]

dp2[2] = max(dp2[1], dp2[2]) + nums[2]

 

마지막에는 print(max(dp2), min(dp1))을 통해 정답을 출력할 수 있다.

 

처음에 풀었을 때는 계속 메모리초과가 나서 뭐가 문제일까 생각하다가 nums에 모든 줄에 [a, b, c]를 저장해놓아서 그런 것 같았다. 

 

굳이 저장을 안해놓고 해도 문제를 해결할 수 있을 것같아 위와 같이 코드를 수정하고 정답을 맞을 수 있었다.

 

 

내 제출

 

 

 

BOJ 13549. 숨바꼭질 3

---

13549번: 숨바꼭질 3

 

 

내 코드

from collections import deque
import sys

input = sys.stdin.readline

n, k = map(int, input().split())
q = deque([(0, n)])
visited = [False] * 100001
visited[n] = True

while q:
    time, x = q.popleft()
    if x == k:
        print(time)
        break

    for nx in [x*2, x-1, x+1]:
        if 0 <= nx < 100001 and not visited[nx]:
            visited[nx] = True
            if nx == x*2:
                q.append((time, nx))
            else:
                q.append((time+1, nx))

bfs로 해결할 수 있었다.

 

현재 위치와 시간을 deque에 저장하면서 진행했다.

 

처음에는 (0, n)을 q에 저장했고, 이를 기점으로 다음 위치와 그 위치에 도달한 시간을 저장했다.

 

이 때, 2*x는 0초가 걸리기 때문에 deque에 (time, nx)로 저장했고, 그 외에 나머지는 1초가 걸리기 때문에 (time+1, nx)로 저장했다.

 

이러다가 deque에서 popleft한 x가 k와 같다면 time을 출력하고 정답을 맞출 수 있었다.

 

 

내 제출

 

 

BOJ 1043. 거짓말

---

1043번: 거짓말

내 코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

know = set(list(map(int, input().split()))[1:])

parties = []
for _ in range(m):
    parties.append(list(map(int, input().split()))[1:])

while True:
    updated = False

    for party in parties:
        if all(person not in know for person in party):
            continue
        for person in party:
            if person not in know:
                know.add(person)
                updated = True

    if not updated:
        break                

answer = 0
for party in parties:
    if all(person not in know for person in party):
        answer += 1

print(answer)

그냥 쉽게 접근해서 풀었다.

 

먼저 지민이의 대해 아는 사람들을 know라는 set에 저장해두었다.

 

그리고 각 파티들의 참가자들을 parties에 저장해 두었다.

 

각 party에 know에 있는 사람이 있으면 그 party에 있는 사람들을 모두 know에 저장했다.

 

위 과정을 know에 사람들이 추가가되지 않을 때까지 반복했다.

(처음에는 이 위 과정을 업데이트가 끝날때까지 반복하지 않고 한번만 했다가 문제를 틀렸다...)

 

그리고 각 party에 대해서 그 party에 오는 사람들 모두가 know에 저장되어 있지 않으면 answer를 +1해주었다.

 

마지막에는 이 answer를 출력하여 정답을 맞을 수 있었다.

 

 

내 제출