백준 2240번 자두나무 JAVA

링크텍스트

설명

풀이 흐름 설명

처음에 나는 이 문제를 누적합 문제로 풀 수 있을지 고민했다.
하지만 이 문제는 연속된 구간의 합을 구하는 것이 아니라 이동 횟수 제한이 존재하기 때문에 단순 누적합으로는 최적의 해를 구할 수 없었다. 그래서 DP를 사용하기로 결정했다.

DP를 설계할 때 처음에는 3차원 배열로 관리할지 2차원 배열로 관리할지 고민했다.
3차원 배열이면 시간, 이동 횟수, 현재 나무 위치를 따로 관리할 수 있지만 위치는 사실 이동 횟수의 짝수/홀수 여부로 자동 결정되므로 2차원 배열로 충분하다는 결론을 내렸다.

dp[i][j] = i초까지 j번 이동했을 때 먹을 수 있는 자두의 최대 개수
j가 짝수이면 1번 나무에 위치
j가 홀수이면 2번 나무에 위치
i초에 떨어진 자두가 현재 위치와 같다면 +1

이 점화식을 바탕으로 반복문을 통해 DP를 갱신하였다.

DP 구현 시 고민과 해결

DP를 구현하면서 가장 먼저 고민한 것은 이동 횟수 0일 때 처리였다.
만약 j=0일 때 dp[i-1][j-1]을 참조하면 배열 인덱스 오류가 발생하기 때문에 j>0일 때만 이전 이동에서 오는 값을 고려하도록 조건을 추가하였다.

또한 DP 배열을 3차원으로 구현할 필요가 없다는 점을 깨달았다.
위치 정보는 이동 횟수의 짝수/홀수 여부로 결정되므로, 2차원 DP만으로도 충분히 문제를 해결할 수 있었다.

풀이 흐름 상세

먼저 자두가 떨어지는 나무 정보를 배열에 저장하였다.
시간 1초부터 t초까지 반복하면서 모든 이동 횟수 j = 0 ~ W에 대해 DP 값을 갱신하였다.
점화식은 다음과 같다.

dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] if j>0) + (현재 위치에 자두가 떨어졌다면 +1)

반복이 끝난 후 dp[t][0~W] 중 최대값을 선택하여 정답으로 출력하였다.

최적화 아이디어

현재 구현은 시간복잡도 O(TW), **공간복잡도 O(TW)를 가진다.
하지만 공간을 1차원 배열로 최적화할 수 있다.
이전 초의 DP 값만 필요하므로 dp[i][j] 대신 dp[j] 하나로 갱신 가능하다.
이 방법을 적용하면 공간복잡도는 O(W)**로 줄일 수 있으며 메모리 효율이 개선된다.
또한 이동 횟수 제한과 짝수/홀수 위치를 활용하면 DP 차원을 줄일 수 있어 코드가 더 간결해진다.

결론

처음에는 누적합 문제로 착각했지만 이동 횟수 제한이 존재하기 때문에 DP 접근이 더 적합했다.
위치 정보가 이동 횟수로 결정된다는 점을 이용하면 3차원이 아닌 2차원 DP로 문제를 해결할 수 있으며 1차원으로 최적화하면 공간 효율을 높일 수도 있다.

이 문제를 풀면서 DP 설계, 점화식 정의, 불필요한 차원 제거와 같은 과정을 체계적으로 연습할 수 있었다. 실제로 코드를 구현하면서 각 초마다 이동 여부와 자두 먹기를 고려하는 흐름을 명확히 이해할 수 있었다.
시간복잡도: O(T*W), 공간복잡도: O(T*W)

회독

• [ x ] 1회
• 2회
• 3회

코드

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 t = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

        int [] arr = new int[t+1];

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

        for(int i=1;i<=t;i++){
            for(int j=0;j<=w;j++){ // 0번 이동 ~ W번 이동까지의 경우를 구함

                dp[i][j] = dp[i-1][j]; // 이번 초 이동 안함

                if(j>0) dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]); // 이번 초 이동

                int tree = 0;

                if(j%2==0) tree = 1; //j는 이동 횟수 짝수번 이동할때만 1번 나무임
                else tree = 2;

                if(arr[i]==tree) dp[i][j]++;
            }
        }

        int max = 0;
        for(int j=0;j<=w;j++){
            max = Math.max(max,dp[t][j]);
        }

        System.out.println(max);
   }
}

개선 코드

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 t = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

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

        int[] dp = new int[w + 1];

        for (int i = 1; i <= t; i++) {
            for (int j = w; j >= 0; j--) {
                int currentTree = (j % 2 == 0) ? 1 : 2;

                if (j > 0) dp[j] = Math.max(dp[j], dp[j - 1]);

                if (arr[i] == currentTree) dp[j]++;
            }
        }

        int answer = 0;
        for (int j = 0; j <= w; j++) {
            answer = Math.max(answer, dp[j]);
        }

        System.out.println(answer);
    }
}