[python] 백준 - 2240. 자두나무

🤔문제 해결

 S1 | 다이나믹프로그래밍

 

1.  답은 X초에 Y번 움직여서 먹은 최대의 자두 갯수! 변수가 2개이니 2차원 리스트를 만든다.
다른 분들의 답을 보면 자두(사람 헷갈림)의 위치까지 저장하여 3차원으로 만든다.
하지만 이동 횟수에 따라 자두(사람)의 위치는 저절로 정해진다.
홀수번 움직이면 2번 나무에, 짝수번 움직이면 1번 나무에 있다.

 

2. 행을 초(0~자두갯수) 열을 움직일 수 있는 횟수(0~W) 만큼 2차원 리스트를 만든다.

dp의 0번째 행은 0초때, 0번째 열은 움직이지 않았을 때

 

3. %중요%

 (1) 받아 먹는 조건:

  a. i초에 자두가 1번에서 떨어지고 이동 횟수가 짝수(j % 2 == 0, 1번 나무에 위치)하면

  b. i초에 자두가 2번에서 떨어지고 이동 횟수가 홀수(j % 2 == 1, 2번 나무에 위치)하면
 i-1초 때 j번 째 위치의 자두 수와 i-1초 때 j-1번 째 위치의 자두 수 중 큰 값에 + 1하여 dp[i][j]를 채운다.

  (2) 안 먹는 조건:

  a. i초에 자두와 자두(사람)이 엇갈릴 때

 i-1초 때 j-1, j 번 째의 max값을 넣으면 된다.

테스트 케이스 DP

💨 DP는 점화식을 세우는 것이 매우 중요하다!

 

💻소스 코드

import sys
if __name__ == "__main__":
    T, W = map(int, input().split())
    plums = [0]
    for i in range(T):
        plums.append(int(sys.stdin.readline()))

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

    for i in range(1, T+1):
        # 한번도 움직이지 않았을 때(dp[i][0]을 채우는 과정)
        if plums[i] == 1:  # 자두가 1번에서 떨어질 때만 받아 먹을 수 있다.
            dp[i][0] = dp[i-1][0] + 1  
        else:  
            dp[i][0] = dp[i-1][0]   

        # 이동 횟수를 1번부터 W 번까지 움직이면서 체크
        for j in range(1, W+1):
            if j > i:
                break
                
            # 자두가 1번에서 떨어지고, 그것을 받아 먹기
            if plums[i] == 1 and j % 2 == 0:
                # 움직여서 받아먹을 것인가, 현재위치에서 받아먹을 것인가
                # 어짜피 이동한 횟수는 같다(지금 이동하거나 이전에 이동했거나)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + 1

            # 자두가 2번에서 떨어지고, 그것을 받아 먹기
            elif plums[i] == 2 and j % 2 == 1:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + 1
                
            # 그 외 - 안먹는다 - 그대로 있거나 움직여서 안먹음
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])

    print(max(dp[-1]))

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

2240번: 자두나무

---

---

---

문제

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

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

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

입력

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

출력

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