BOJ2240 자두나무

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

2240번: 자두나무

풀이시간: 1시간이상 걸려서 힌트를 참고하여 품

난이도: 골드5

 

아래는 나의 코드이다. 처음 접근 법은 자두까 떨어지는 나무가 바뀔때를 기준으로 입력값을 끊어서 생각했다.

예를 들면 2 1 1 2 2 1 1 순으로 자두가 떨어지면 1 2 2 2 로 변환하여서 생각하였다. 이 방법대로 풀어보니 뒤로갈수록 허점들이 발견이 되었고 수정을 하여도 몇몇 케이스에서 제대로 작동을 하지 안았다. 이 접근법 때문에 시간을 많이 잡아 먹었다.

그래서 새로 시작하였다. 이번에는 DP테이블을 초,이동으로 설계를 하였다.

아래 코드를 보면 초를 기준으로 반복문을 돌리고 그 안에서 횟수에 따라서 반복문을 돌린다.

 

점화식은 자두가 떨어지는 나무와 현재위치가 같다면 DP[이전초][이동횟수(k)-1],DP[이전초][이동횟수(k)] 중 큰값에 1을 더해준 값이 DP[현재초][k]가 된다. 만약 다르다면 1을 더해 주지 않는다. k가 0 일 경우에는 이전값이 존재하지 않아 떨어지는 나무가1인지만 체크해주면 된다. k가 짝수라면 1번나무에 위치하게 되고 홀수라면 2번 위치에 존재하게 된다. 1초에 한번만 이동할 수 있기에 DP[이전초][이동횟수(k)-1],DP[이전초][이동횟수(k)] 두값만 비교하여 주면 된다.

import sys
T,W =map(int,sys.stdin.readline().split())
plum=[]
for i in range(T):
    plum.append(int(sys.stdin.readline()))

DP=[[0 for _ in range(W+1)] for _ in range(T+1)]

for i in range(T):
    for k in range(W+1):
        if plum[i]==1:
            if k==0:
                DP[i+1][k] = DP[i][k]+1
            elif k%2==0:
                DP[i+1][k] = max(DP[i][k]+1,DP[i][k-1]+1)
            else:
                DP[i+1][k] = max(DP[i][k],DP[i][k-1])
        else:
            if k==0:
                DP[i+1][k] = DP[i][k]
            elif k%2==0:
                DP[i+1][k]=max(DP[i][k],DP[i][k-1])
            else:
                DP[i+1][k] =max(DP[i][k]+1, DP[i][k-1]+1)

print(max(DP[-1]))