2240(자두나무) - 해결

자두나무

 

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

 

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

 

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

---

처음에는 dfs방식을 쓸까 했지만 너무 복잡하고 오래걸릴것 같아서 보니 역시 DP

그래서 어떻게 할까 생각하다가 행을 이동 횟수 열을 시간으로 하였다.

처음 시간은 바로 초기화하고 1~T-1 초까지 확인하여 다음 시간의 자두 획득을 판단하였다.

이동 횟수에 따라 자리가 정해지기 때문에 이를 활용하여 자두을 얻을 수 있을 지 아닐지를 판단하였다.

그리고 마지막 열에서 가장 큰것을 뽑았다.

 

import sys
input = sys.stdin.readline

T, W = map(int,input().split())

# 자두 떨어지는 위치
zado_loc = [int(input()) for _ in range(T)]
# 행은 움직이는 횟수
# 열은 시간
dp = [[-1]*T for _ in range(W+1)]

# 처음 시간은 바로 초기화
# 1이면 안움직이는 곳이 1 움직으면 0
if zado_loc[0] == 1:
    dp[0][0] = 1
    dp[1][0] = 0
else:
    dp[0][0] = 0
    dp[1][0] = 1

# 처음 위치
loc = 1
# 시간은 T-1까지
for j in range(T-1):
    # 움직인 횟수를 확인
    for i in range(W+1):
        # -1보다크면 해당 횟수로 움직였다는 뜻
        if dp[i][j] >= 0:
            # 움직인 횟수를 2로 나눈 나머지가 0이면 1에 위치하고 아니면 2에 위치한다
            # 그리고 1을 더하는 것은 나머지가 0,1이기때문

            # 안 움직였을 때
            # 자두가 해당 위치에 떨어지면 +1을 해서 최대값 비교
            if (i % 2) + 1 == zado_loc[j+1]:
                dp[i][j+1] = max(dp[i][j+1],dp[i][j] + 1)
            # 자두가 반대에 떨어지면 자두를 못 얻기 때문에
            else:
                dp[i][j+1] = max(dp[i][j+1],dp[i][j])

            # 범위를 넘는것은 패스
            if i + 1 > W:
                continue
            # 움직였을 때
            if ((i + 1) % 2) + 1 == zado_loc[j+1]:
                dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + 1)
            else:
                dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j])

# 마지막 열에서 가장 큰 값이 정답
result = 0
for i in range(W+1):
    if result < dp[i][T-1]:
        result = dp[i][T-1]

print(result)