백준 2240번 자두나무

 

코드

import sys
input = sys.stdin.readline

T, W = map(int, input().split())
drop = [0]
for _ in range(T):
    drop.append(int(input()))

dp = [[0 for _ in range(W+1)] for _ in range(T+1)]
for t in range(1, T+1):
    for w in range(W+1):
        j = 1 if drop[t] == w % 2 + 1 else 0
        dp[t][w] = max(dp[t-1][0:w+1]) + j
print(max(dp[T]))

 

풀이

처음에는 알고리즘 분류를 보지 않고 풀기 시작했으며, T라는 유한한 횟수동안 반복하고 이전의 선택이 이후의 선택에 영향을 미친다는 점 때문에 '백트래킹' 알고리즘으로 풀어보았다. 백트래킹 로직은 자두의 위치를 저장할 리스트를 두고, 자두의 직전 위치에 따라 현재 위치를 바꿀지 유지할지를 판단하는 방식으로 설정했다. 그런데 '시간초과'라는 결과를 얻었다. 코드 중간 중간에 print문을 통해 어느 지점에서 백트랙을 하는지 살펴본 결과, 로직 중 '직전 위치와 현재 트리의 위치가 다를 경우'에 두 액션 중 하나를 취함 & 두 가지 액션 중 첫번째가 '위치를 이동하지 않음' 일 경우에서 비효율적이라는 것을 알게 되었다. 백트랙을 하게 될 때 직전 위치와 현재 트리가 달라지는 가장 최근 지점으로 이동하는데, 굳이 그 지점으로 이동하는 것이 직관적으로 올바르지 않다. 또 그 지점으로 이동하고 나서도 로직에 의해 '이동하지 않음'을 우선적으로 택하기 때문에 정답을 찾는 과정에서 빙빙 둘러가게 되는 것이다.

구글링을 해보면서 '다이나믹 프로그래밍'으로 풀어야 한다는 힌트를 얻을 수 있었다.

그런데 문제는 dp 점화식에 대한 감이 전혀 오지 않았다. w(대문자 W는 문제 제시문에서 나왔듯 움직일 수 있는 최대 횟수이다.)를 현재까지 움직인 횟수라고 정의했을 때 [t][w]를 구할 때 [t-1][w-1]와 [t-1][w]에서만 유도해야 하는 줄 알았던 것이다. 그런데, 문제를 다시 읽어보니 헷갈렸던 원인을 파악할 수 있었다. 문제에서 '자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다.' 라고 되어 있었다. 즉, 자두는 나무1과 나무2 사이를 왔다갔다하는 횟수가 1초 동안 0번일 수도, 1번일 수도, 2번일 수도, 혹은 움직일 수 있는 최대 횟쉰 W번일 수도 있었던 것이다. 결론부터 말하면 dp 점화식은 dp[t][w] = max(dp[t-1][0:w+1]) + j (여기서 j는 drop[t] == w % 2 + 1이면 1, 아니면 0)이었다. 자두가 t=0(초기)에 서있는 위치는 나무1이기 때문에 w(움직인 횟수)가 짝수이면 현재 위치는 나무1(그대로)이고, 홀수이면 현재 위치는 나무2가 된다. '이동'은 나무1->나무2 or 나무2->나무1이기 때문에, t 시점에 짝수번 이동하면 무조건 나무1, 홀수번 이동하면 무조건 나무2에 도달하게 된다. 그렇기 때문에 (t-1)시점에 몇번을 움직였든, 위치가 어디였든지 간에 t 시점에 w가 홀수인지 짝수인지에 따라 t 시점의 위치가 결정되고, 이를 토대로 자두가 떨어지는 나무에 잘 서있는지 여부를 판단하여 1을 더할지 말지를 결정하면 되는 것이다.