[파이썬, 자바] 백준 2240 : 자두나무 (골드5)

[파이썬, 자바] 백준 2240 : 자두나무 (골드5)

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

---

풀이

방향성 생각

• 바텀업 DP 정석
• state는 3개로 구분된다.
  • 현재 위치 n, 현재 나무 위치 l, 이동 횟수 k
  • dp[k][l][n]으로 3차원 DP 테이블 작성
• n 에서 n+1로 넘어갈 때 l을 바꿀지 안바꿀지에 따라서 k값 증가유무가 결정된다.
• 이동하지 않으면 l도 고정이고, 이동하면 k가 증가하면서 l은 토글된다.
• k값이 K와 같으면 다음 K+1은 없으므로, 인덱스 에러를 방지해주는 조건문
  추가.

# 기본적으로 다음 노드에 도착하면 사과 유무로 + 1 해주기

# 옆 나무로 이동하는 경우 k+1되며 l은 toggle된다.
dp[k+1][l][n+1] = max(dp[k+1][l][n], dp[k][l^1][n] + int(arr[n+1]==l))
# 옆 나무로 이동하지 않는 경우 이전 값과 같다.
dp[k][l][n+1] = max(dp[k][l][n+1], dp[k][l][n] + int(arr[n+1]==l))

 

---

파이썬

import sys
input = lambda : sys.stdin.readline().rstrip()

N,K = map(int, input().split())
arr = [0] + [int(input())-1 for _ in range(N)]

dp = [[[0]*(N+1) for _ in range(2)] for _ in range(K+1)]
dp[0][0][1] = int(arr[1] == 0)
dp[1][1][1] = int(arr[1] == 1)

for n in range(1,N):
    for k in range(K+1):
        for l in range(2):
            if k<K:
                dp[k+1][l][n+1] = max(dp[k+1][l][n], dp[k][l^1][n] + int(arr[n+1]==l))
            dp[k][l][n+1] = max(dp[k][l][n+1], dp[k][l][n] + int(arr[n+1]==l))

print(max(dp[k][l][-1] for k in range(K+1) for l in range(2)))

자바

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N+1];
        for (int i=1; i<N+1; i++) {
            arr[i] = Integer.parseInt(br.readLine())-1;
        }

        int[][][] dp = new int[K+1][2][N+1];
        dp[0][0][1] = (arr[1]==0 ? 1 : 0);
        dp[1][1][1] = (arr[1]==1 ? 1 : 0);

        for (int n=1; n<N; n++) {
            for (int k=0; k<K+1; k++) {
                for (int l=0; l<2; l++) {
                    if (k<K) {
                        dp[k+1][l][n+1] = Math.max(dp[k+1][l][n], dp[k][l^1][n] + (arr[n+1]==l ? 1 : 0));
                    }
                    dp[k][l][n+1] = Math.max(dp[k][l][n+1], dp[k][l][n] + (arr[n+1]==l ? 1 : 0));
                }
            }
        }

        int answer = 0;
        for (int k=0; k<K+1; k++) {
            for (int l=0; l<2; l++) {
                answer = Math.max(answer, dp[k][l][N]);
            }
        }
        System.out.println(answer);
    }
}

---

코멘트

• .