문제

BOJ 2240: 자두나무 https://www.acmicpc.net/problem/2240

풀이

조건

• 매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다.
• 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다.
• 자두는 T(1≤T≤1,000)초 동안 떨어지게 된다.
• 최대 W(1≤W≤30)번만 움직일 수 있다.
• 처음에는 1번 자두나무 아래에 위치해 있다고 한다.

풀이 순서

• 시간(T)이 행, 이동 횟수(W)이 열인 2차원 배열 dp를 사용한다.
• 1초부터 T초까지 시간 순으로 dp 배열의 값을 구한다.
• 해당 시간에 이동한 횟수 순으로 dp 배열의 값을 구한다.
  • 이동 안했을 때 (w == 0)
    • 현재 위치와 열매가 떨어지는 위치가 같다면 이전 시간의 같은 이동 횟수의 값 +1
    • 위치가 다르면 이전 시간의 같은 이동 횟수의 값 그대로
  • 이동 했을 때 (w >= 1)
    • 이동한 횟수가 짝수, 홀수인지에 따라 현재 위치를 구한다.
      • 짝수 : 1번 나무 밑
      • 홀수 : 2번 나무 밑
    • 현재 위치와 열매가 떨어지는 위치가 같다면
      • 가만히 있는 경우 : dp[t-1][w] + 1
      • 움직인 경우 : dp[t-1][w-1]
      • 위의 두 경우 중 더 큰 값을 dp[t][w]에 저장한다.
    • 현재 위치와 열매가 떨어지는 위치가 다르다면
      • 가만히 있는 경우 : dp[t-1][w]
      • 움직인 경우 : dp[t-1][w-1] + 1
      • 위의 두 경우 중 더 큰 값을 dp[t][w]에 저장한다.

코드

Java

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

public class Main {

	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[] tree = new int[T + 1];
		for (int i = 1; i <= T; i++) {
			tree[i] = Integer.parseInt(br.readLine());
		}

		int pos = 1;
		int[][] dp = new int[T + 1][W + 1];
		int answer = 0;
		
		// 시간 순으로
		for (int t = 1; t <= T; t++) {
			int treePos = tree[t];
			
			// 현재 시간에 이동한 횟수 순으로
			for (int w = 0; w <= W; w++) {
				// 이동 안했을 때
				if (w == 0) {
					pos = 1;
					// 현재 위치(1)와 열매 위치가 같을 때
					if (treePos == pos) {
						dp[t][w] = dp[t - 1][w] + 1;
					} 
					// 다를 때
					else {
						dp[t][w] = dp[t - 1][w];
					}
					
					continue;
				}
				
				// 이동 했을 때
				// 짝수번째 이동 -> 1번 나무 밑
				if(w % 2 == 0) {
					pos = 1;
					// 현재 위치와 나무가 일치
					if(pos == treePos) {
						dp[t][w] = Math.max(dp[t-1][w] + 1, dp[t-1][w-1]);
					} 
					// 위치 불일치
					else {
						dp[t][w] = Math.max(dp[t-1][w-1] + 1, dp[t-1][w]);
					}
				} 
				// 홀수번째 이동 -> 2번 나무 밑
				else {
					pos = 2;
					// 현재 위치와 나무가 일치
					if(pos == treePos) {
						dp[t][w] = Math.max(dp[t-1][w] + 1, dp[t-1][w-1]);
					} 
					// 위치 불일치
					else {
						dp[t][w] = Math.max(dp[t-1][w-1] + 1, dp[t-1][w]);
					}
				}
				
				answer = Math.max(answer, dp[t][w]);		
			}
			
		}
		
		System.out.println(answer);
	}
}

정리

• 2차원 배열로 해결해야 한다는 점은 생각해 냈는데 정확한 구현을 하지 못했다.