[백준] 2240. 자두나무 - 골드5

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

2240번: 자두나무

문제 요약

 

매 초마다 두 개의 자두 나무 중 하나의 나무에서 열매가 떨어진다. 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아 먹을 수 있다. 두 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 움직일 수 있다.

자두가 떨어지는 시간과 움직일 수 있는 최대의 움직임, 그리고 몇 초에 어느 나무에서 자두가 떨어질지에 대한 정보가 주어질 때 자두가 받을 수 있는 자두의 최대 개수를 구해내는 프로그램을 작성하시오.

- 자두는 시작할 때 1번 자두나무 아래에 위치해 있다.

 

문제 해결 아이디어

 

움직임이 0일 때는 1번, 1일 때는 2번, 2일 때는 1번 이런 식으로 짝수 번일 때 1번 나무 아래 있고, 홀수 번일때 2번 나무 아래에 있다.

비교를 편하게 하기 위해서 자두가 떨어지는 나무의 번호를 -1씩 받았다. 즉 0번과 1번 나무다.

 

움직이지 않았을 때, 즉 움직임이 0일 때에는 초에 따라서 떨어지는 나무가 0번 나무인지만 확인해 주면 되었다. 나무가 0번 나무일 때에는 이전 카운트에 +1을 했다.

 

움직임이 i일 때를 생각해 본다.

움직임이 i일 때, i % 2 가 나무의 번호와 같을 때라면 (자두가 떨어진다)

- 1초 전까지 움직임이 i-1이다가 이번에 움직여서 자두를 받을 수 있을 때 (dp[i-1][j-1] + 1)

- 움직이지 않고 자두를 받을 때 (dp[i][j-1] + 1)

의 두 경우로 나눌 수 있다.

 

마찬가지로 이번에 자두가 떨어지지 않는다면

- 1초 전까지 움직임이 i-1이다가 이번에 움직였는데 자두를 못 받을 때 (dp[i-1][j-1])

- 움직이지 않았지만 자두도 못 받을 때 (dp[i][j-1])

의 두 경우로 나눌 수 있다.

 

이 경우들에 대해 최대값을 구한다.

 

이렇게 모든 움직임과 초에 대해 최대값을 구한 뒤에는 0번 움직여서 최대가 될 수 있고, 4번 움직여서 최대가 될 수 있으므로 움직임의 결과끼리 비교해 주어 최종 최대값을 구해 준다. 

 

 

완성된 코드

 

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

public class Main {
	/*
	 * 76ms
	 */
	
	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[] num = new int[T + 1];
		for (int i = 1; i <= T; i++) {
			num[i] = Integer.parseInt(br.readLine()) - 1; // 현재 위치와 자두나무 번호 비교하기 쉬우라고
		}

		int[][] dp = new int[W + 1][T + 1];

		for (int i = 1; i <= T; i++) {
			if (num[i] == 0)
				dp[0][i] = dp[0][i - 1] + 1;
		}

		for (int i = 1; i <= W; i++) {
			for (int j = 1; j <= T; j++) {
				if (i % 2 == num[j]) // 현재 위치가 자두가 떨어지는 나무라면 
					dp[i][j] = Math.max(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1); // 움직이지 않고 +1, 움직여서 +1 중 최대값 구하기
				else // 자두 떨어지지 않는다면
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - 1]); // 움직이지 않거나 움직이거나 둘 중 하나 최대값 구하기
			}
		}

		int answer = 0;
		
		// 움직이지 않고 최대일 수 있으므로 모든 움직임에 대해 최대값을 구해 본다
		for (int i = 0; i <= W; i++) {
			answer = Math.max(dp[i][T], answer);
		}
		
		System.out.println(answer);
	}
}