[python] 백준 2240 자두나무

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

2240번: 자두나무

문제 해결

• 정답이 이지선다형 문제이고 0, 1 둘 중 하나이다.
• 처음에 1을 선택하는 곳에 있다고 한다.
• 그러면 dp를 이용해 이동을 시키는 것을 목표로 한다.
• 처음에는 (w, t, answer) # 움직인 횟수, 시간, 정답 을 이용해서 dp[i][t]의 최댓값의 최댓값을 구하려고 했다.
• 하지만 움직인 횟수와 정답 선택간에 연관이 있었고 이를 표현하기 위해서는 오히려 더 간단한 코드가 편했다. (움직인 횟수가 홀수이면 2번을 선택한 것이고, 움직인 횟수가 짝수이면 1번을 선택한 것이다.)
• 이를 이후로 (t,w)리스트를 만들었고 정답이 1이고 w%2==0 일 때나 정답이 2이고 w%2==1일 때 1점을 더 주고 아닐 때는 이전 값의 최댓값을 가져오는 식으로 코드를 짰다.

 

CODE

import sys
input = sys.stdin.readline

t,w = map(int, input().split())
answer = [0]
for _ in range(t):
    x = int(input())
    answer.append(x)
dp = [[0]*(w+1) for _ in range(t+1)]

for i in range(1,t+1):
    if answer[i] == 1: # 시작점이 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 answer[i] ==2 and j%2==1:
            dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + 1
        elif answer[i] == 1 and j%2 ==0:
            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]))