[JAVA] BJ 2240 자두나무

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

 

문제

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

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

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

 

입출력

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

 

풀이

먼저 점화식을 구했다.

점화식을 구하면서 두 가지를 고려했다.

- 움직이지 않고 자두 먹기

- 1회 움직이고 자두 먹기

 

위 조건을 구현하려면 dp배열은 2차원배열로 w+1행, t열의 배열이 필요했다.

그리고 dp[i][j] = max(dp[i-1][a] +1, dp[i][b])

a = 현재 위치와 다른 곳에 떨어진 자두중 가장 가까운지점

b = 현재 위치와 같은 곳에 떨어진 자두 중 가장 가까운 지점

dp[1][1]을 구할 때, 즉 1회이동, 1번자리에 떨어진 경우

- 0회이동, 2번자리에 떨어진 최댓값에 1을 더한 값 dp[0][4] = 0,  0 + 1 = 1

- 1회 이동, 1번자리에 떨어진 최댓값 dp[1][2] = 2, 2 + 1 = 3

중 큰 값이 최댓값이 되어야 한다 1, 3중 큰 값

==> dp[i][j] = Math.max(dp[i-1][a], dp[i][b])

 

여기서 dp[1][5]의 값이 dp[1][4]보다 작다고 갱신하면 안된다.

현재dp[i][j]의 값은 무조건 먹은 경우이기 때문에 먹지 않았는데 갱신처리를 해버리면

이후 계산 시 잘못된 값을 구하게 된다.

 

따라서 최대이동에서 최대 answer값을 찾아야 한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_2240_자두나무 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

        int[] info = new int[t];
        int[][] dp = new int[w+1][t];
        int count = 1;

        for(int i = 0; i < t; i++){
            info[i] = Integer.parseInt(br.readLine());
            if(info[i] == 1) dp[0][i] = count++;
        }
        int answer = 0;
        for(int i = 1; i <= w; i++){
            for(int j = 0; j < t; j++){
                int idx = j-1;
                while(idx >= 0){
                    if(info[j] == info[idx]){
                        dp[i][j] = dp[i][idx] + 1;
                        break;
                    }
                    idx--;
                }
                idx = j-1;
                while(idx >= 0){
                    if(info[j] != info[idx]){
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][idx] + 1);
                        break;
                    }
                    idx--;
                }
                if(dp[i][j] == 0) dp[i][j] = 1;
            }
        }
        for(int i = 0; i < t; i++){
            answer = Math.max(answer, dp[w][i]);
        }
        System.out.println(answer);
    }
}