[백준] 2240번 - 자두나무

 

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

2240번: 자두나무

 

 

어떤 시간에 어떤 위치에 있어야 자두를 최대한 많이 받을 수 있는지 계산하는 문제이다.

 

해당 문제도 동적계획법 문제로 풀면 해결이 된다.

 

일단 예제에서 제시한 예시를 기준으로 어떻게 6개라는 숫자가 나오는지 확인해보자.

 

여러가지 경우의 수가 있겠지만 대표적으로 두개의 경우의 수가 있다.

 

다른 경우의 수를 조합해봐도 최대 6개 초과의 자두를 받을수는 없으므로 

 

최대 자두 획득 개수는 6개가 된다고 할 수 있다.

 

DP 문제는 점화식을 얼마나 잘 세우느냐에 해당 문제를 풀 수 있느냐 없느냐가 결정된다.

 

점화식을 세우기 전에 문제가 제시한 규칙을 생각해보자.

 

규칙을 기반으로 아래와 같은 대략적인 알고리즘을 생각해 볼 수 있다.

 

대략적인 점화식을 세워보자.

 

p = 현재 사람의 위치

t = 현재 시간

r = 현재 남은 움직임 회수

 

 

-현재시간에 자두가 떨어지는 나무의 번호가 1인경우

 

dp[1][t][r] = max(dp[1][t-1][r] +1,dp[2][t-1][r-1] +1)

 

dp[2][t][r] = max(dp[1][t-1][r-1],dp[2][t-1][r] )

 

 

-현재시간에 자두가 떨어지는 나무의 번호가 2인경우

 

dp[1][t][r] = max(dp[1][t-1][r],dp[2][t-1][r-1] )

 

dp[2][t][r] = max(dp[1][t-1][r-1] + 1,dp[2][t-1][r] + 1)

 

 

위와 같은 점화식으로 코드를 구성하면 아래와 같이 구성해줄 수 있다.

 

1. C++

#include <iostream>

using namespace std;


int T,W;
int input[1002];
int dp[3][32][1002];
int max_val;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> T >> W;

    for (int i = 1; i <= T; i++) cin >> input[i];
    
    // T W 
    for (int i = 1; i <= T; i++) {
        for (int j = 1; j <= W+1; j++) {
            
            if (input[i] == 1) {

                dp[1][j][i] = max(dp[1][j][i-1] + 1 , dp[2][j-1][i-1] + 1);
                dp[2][j][i] = max(dp[1][j-1][i-1], dp[2][j][i-1]);

            } else {
                
                if (i == 1 && j == 1) continue;
                
                dp[1][j][i] = max(dp[1][j][i-1], dp[2][j-1][i-1]);
                dp[2][j][i] = max(dp[1][j-1][i-1] + 1, dp[2][j][i-1] + 1);
            }
        }
    }

    for (int i = 1; i <= W+1; i++) {
        max_val = max(max_val,max(dp[1][i][T],dp[2][i][T]));
    }

    cout << max_val;


     

    return 0;
}

 

위를 보면 j 가 w+1 까지 loop문을 도는것을 볼 수 있는데, 이것은 움직일수 있는 거리가 0이더라도

 

전의 위치와 현재의 위치가 같다면 자두를 모으는데에는 제약이 없기 때문이다.

 

 

2. JAVA 

 

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

public class Main {
	
	static int T,W;
	static int[][][] dp;
	static int[] input;
	static int maxCount;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(stk.nextToken());
		W = Integer.parseInt(stk.nextToken());
		
		input = new int[T+1];
		dp = new int[3][T+1][W+2];
		
		for (int i = 1; i <= T; i++) {
			input[i] = Integer.parseInt(br.readLine());
		}
		
		
		for (int i = 1; i <= T; i++) {
			for (int j = 1; j <= W+1; j++) {
				
				if (input[i] == 1) {
					dp[1][i][j] = Math.max(dp[1][i-1][j] + 1, dp[2][i-1][j-1] + 1);
					dp[2][i][j] = Math.max(dp[1][i-1][j-1], dp[2][i-1][j]);
				} else {
					if (i == 1 && j == 1) continue;
					
					dp[1][i][j] = Math.max(dp[1][i-1][j], dp[2][i-1][j-1]);
					dp[2][i][j] = Math.max(dp[1][i-1][j-1] + 1, dp[2][i-1][j] + 1);
				}
			}
		}
		
		for (int i = 1; i <= W+1; i++) maxCount = Math.max(dp[1][T][i], dp[2][T][i]);
		
		bw.write(maxCount + "");
		bw.close();
		br.close();
		
	}
}