[백준] 2240 - 자두나무

1. 문제

2240번: 자두나무

2. 개요

자두나무 1, 2가 있고 매 초마다 어느 한 그루에서 열매가 떨어진다.

자두가 자두나무 밑에 서 있다면 열매를 먹을 수 있다.

자두의 이동 가능 횟수가 주어질 때 자두가 먹을 수 있는 열매 수의 최댓값을 구하는 dp문제.

3. 코드 및 추가내용

import sys

T, W = map(int, sys.stdin.readline().split())

dp = [[0 for i in range(W+1)]]

for i in range(T):
    dp.append([d for d in dp[-1]])
    pos = int(sys.stdin.readline())

    if pos == 1:
        dp[i+1][0] = dp[i][0] + 1

        for j in range(2, W+1, 2):
            dp[i+1][j] = max(dp[i][j], dp[i][j-1]) + 1

    else:
        for j in range(1, W+1, 2):
            dp[i+1][j] = max(dp[i][j], dp[i][j-1]) + 1
        
print(max(dp[-1]))

고려해야 할 점은 열매가 떨어지는 나무 위치와 이동여부이다.

열매가 1번 나무에서 떨어진다면 움직이지 않은 경우에 개수를 +1, 2번 나무 밑에 있다가 이동한 경우 +1을 할 수 있다.

반대로 2번 나무에서 열매가 떨어진다면 1번 나무에 있다가 이동한 경우에 개수를 +1 할 수 있다.

dp배열의 i행의 원소들은 i초 후 j번 이동한 경우 먹을 수 있는 열매 수의 최댓값을 메모한다.

1번 나무 밑에서 이동하면 2번 나무 밑, 2번 나무 밑에서 이동하면 다시 1번 나무 밑이 반복되므로 각 행의 짝수 인덱스는 1번 나무 밑을 나타낼 것이고, 홀수는 2번 나무 밑을 나타내게 된다.

초마다 열매가 떨어지는 곳이 입력으로 들어오면 dp 리스트에 새로운 행 전 행과 같은 값으로 판다.

1번 나무에서 떨어진다면 0번 인덱스를 +1 하고 나머지 짝수 인덱스를 확인한다.

2번 나무에서 떨어졌다면 0번 인덱스 작업을 건너뛰고 홀수 인덱스만 확인한다.

직전에 같은 자리에 있었을 때와 다른 자리에 있었을 때의 얻은 개수를 비교해 최댓값 +1 을 메모하는 작업을 반복한 뒤 마지막 행의 최댓값을 출력한다.