[백준] 2240번 : 자두나무

2240번: 자두나무

2240번: 자두나무

🤔 문제분석

dp 테이블을 T시간에 n번 움직였을때 자두를 먹을 수 있는 최대값을 갱신하면 된다.

1번 위치에 있을때에는 짝수번 움직인것이고, 2번 위치에 있을때에는 홀수번 움직인 것으로 생각하여 문제를 접근한다.

바텀엄 방식과 탑다운 방식 모두 문제 풀이를 하였으니 아래의 코드를 참고하자.

아래의 코드를 보면 탑다운 방식의 점화식인데 자두나무의 위치가 일치할경우 eat_value값을 1로 갱신시키고, 움직인경우와 움직이지 않은 경우 값중 최대값을 갱신한다.

eat_value = 0
    if cnt % 2 == 1 and jadu[index] == 2: # 2에 있는경우
        eat_value = 1
    
    if cnt % 2 == 0 and jadu[index] == 1: # 1에 있는경우
        eat_value = 1
    
    dp[index][cnt] = max(dp[index][cnt], dfs(index+1, cnt) + eat_value)
        
    if W >= cnt + 1:
        dp[index][cnt] = max(dp[index][cnt], dfs(index+1, cnt + 1) + eat_value)

💻 코드

바텀업

import sys
input = sys.stdin.readline

T, W = map(int, input().split())
jadu = [int(input()) for _ in range(T)]
dp = [[0 for _ in range(W+1)] for _ in range(T)]

for i in range(T):
    if jadu[i] == 1:
        dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] = dp[i-1][0]
    for j in range(1, W+1):
        if j % 2 == 1 and jadu[i] == 2:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + 1
        elif j % 2 == 0 and jadu[i] == 1:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + 1
        else:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])

print(max(dp[T-1]))

탑다운

import sys
input = sys.stdin.readline

T, W = map(int, input().split())
jadu = [int(input()) for _ in range(T)]
dp = [[-1 for _ in range(W+1)] for _ in range(T)]

def dfs(index, cnt):
    if index >= T:
        return 0
    
    if dp[index][cnt] != -1:
        return dp[index][cnt]
    
    eat_value = 0
    if cnt % 2 == 1 and jadu[index] == 2: # 2에 있는경우
        eat_value = 1
    
    if cnt % 2 == 0 and jadu[index] == 1: # 1에 있는경우
        eat_value = 1
    
    dp[index][cnt] = max(dp[index][cnt], dfs(index+1, cnt) + eat_value)
        
    if W >= cnt + 1:
        dp[index][cnt] = max(dp[index][cnt], dfs(index+1, cnt + 1) + eat_value)
        
    return dp[index][cnt]

print(max(dfs(0, 0), dfs(0, 1)))

🎯 피드백 및 개선사항

움직임 횟수를 이용하여 위치를 파악하는 방법을 알게 되었습니다. 또한 다이나믹 프로그래밍 문제를 풀때에는 dp 테이블을 어떻게 설계 하느냐에따라서 문제의 접근 방식이 달라지는것을 몸소 느꼈습니다. 많은 문제를 접근해보고, 어떻게 dp테이블을 세울지에대한 전략을 열심히 배워나가야 될 것 같습니다. 😅