[백준2240/골드5] 자두나무 - Python

https://www.acmicpc.net/problem/2240

 

이문제를 풀면서 가장 어려웠던 점은 dp 테이블을 어떻게 설계해야하는지에 대한 고민이었다.

처음에는 dp 테이블에 저장할 값을

1. T 시간만큼 순회하는 동안 현재 시간까지의 이동 수

2. 현재 위치

3. 그 이동 수와 현재 위치에 따라 얻을 수 있는 최대 자두의 수

이렇게 저장하려고 생각했다.

하지만 이동 수에 따라서 현재 나무 위치와 자두 최댓값을 어떻게 점화식을 세울지 너무 헷갈렸다.

그래서 처음부터 다시 생각했다.

 

먼저

1. 처음 위치는 똑같이 1번 나무에서 시작

2. 만약에 3번 이동했다면, 1 -> 2 -> 1 -> 2 로 2번 나무

2-2. 따라서 현재 나무 위치를 dp 테이블에 저장할 필요는 없음 (이동 횟수에 따라서 알 수 있으므로)

3. 그렇다면 알아야할 값은

3-1. T 시간만큼 순회하는 동안 현재 시간까지의 이동 수

3-2. 그 이동 수와 현재 위치에 따라 얻을 수 있는 최대 자두의 수

이렇게 정리된다.

 

따라서 dp는 T초 동안 W번 이동하는 이차원 배열로 설정했다.

# dp[i][j]: i초까지 j번 이동했을 때 최대 자두 수
dp = [[0] * (W + 1) for _ in range(T + 1)]

 

 

그리고 T * W 순회하면서 최대 자두의 수를 갱신했다.

for i in range(1, T + 1):
    for j in range(W + 1):
    
        # 현재 자두가 떨어지는 나무
        plum = plums[i - 1]
		
        # 처음 위치(j == 0) 인 경우
        # : 이동을 하지 않았으므로 항상 나무 1번에 있는 상황.
        if j == 0:
        	# 1번 나무에서 자두가 떨어지면 받음
            if plum == 1:
                dp[i][j] = dp[i - 1][j] + 1
            # 아니면 못받음
            else:
                dp[i][j] = dp[i - 1][j]
                
        # 이동한 경우
        # : 자두가 있는 나무와 일치하면 받음
        # : 이동을 하지 않은 상태 (dp[i-1][j])와, 직전 초에 이동해서 현재 위치로 온 경우 (dp[i-1][j-1]) 중 큰 값을 가져옴.
        else:
            if plum == (j % 2) + 1:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1])

 

지금까지 풀어본 디피 문제중에 제일 어렵고 오래걸렸다!