[Baekjoon] 자두나무

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

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

public class Main {

    static int answer;
    static int T, W;
    static int[] input;

    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }

    static void sol() {
        int[][] dp = new int[T + 1][W + 1];
        for (int time = 1; time <= T; time++) {
            int pointTree = input[time];

            for (int moveingCount = 0; moveingCount <= time && moveingCount <= W; moveingCount++) {
                if (moveingCount == 0) {
                    dp[time][0] = dp[time - 1][0] + (pointTree == 1 ? 1 : 0);
                    continue;
                }

                int currentTree = moveingCount % 2 == 0 ? 1 : 2;
                int score = pointTree == currentTree ? 1 : 0;

                dp[time][moveingCount] = Math.max(dp[time - 1][moveingCount], dp[time - 1][moveingCount - 1]) + score;
            }
        }

        for (int movingCount = 0; movingCount <= W; movingCount++) {
            answer = Math.max(answer, dp[T][movingCount]);
        }
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        T = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        input = new int[T + 1];

        for (int i = 1; i <= T; i++) {
            int num = Integer.parseInt(br.readLine());

            input[i] = num;
        }
    }

    static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(answer));
        bw.close();
    }
}

주요 개념

• DP

풀이 방법

• 나무가 세 그루 이상이라면 3차원 DP로 해결해야겠지만 두 그루이기 때문에 2차원 DP로 해결한다.

• DP[현재 시간][움직인 횟수] 로 설정하고, 시작 위치는 1번 나무로 고정되어있기 때문에 움직인 횟수 만으로 현재 위치를 파악할 수 있다.