[백준] 2240번 '자두나무' - Java

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

2240번: 자두나무

---

문제

---

코드

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int t = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		
		int[][] dp = new int[t+1][w+1];
		
		for(int i = 1 ; i <= t ; i++) {
			int p = Integer.parseInt(bf.readLine());
			
			for(int j = 0 ; j <= w ; j++) {
				if(j == 0) {
					if(p == 1) {
						dp[i][j] = dp[i-1][j] + 1;
					} else {
						dp[i][j] = dp[i-1][j];
					}
					continue;
				}
				
				if(j % 2 == 0) {
					if(p == 1) {
						dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j] + 1);
					} else {
						dp[i][j] = Math.max(dp[i-1][j-1] + 1, dp[i-1][j]);
					}
				} else {
					if(p == 1) {
						dp[i][j] = Math.max(dp[i-1][j-1] + 1, dp[i-1][j]);
					} else {
						dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j] + 1);
					}
				}
			}
		}
		int ans = 0;
		for(int i = 0 ; i <= w ; i++) {
			ans = Math.max(ans, dp[t][i]);
		}
		
		bw.write(Integer.toString(ans));
		
		bf.close();
		bw.flush();
		bw.close();
	}
}

위 코드의 다이나믹 프로그래밍 수행결과는 표와 같습니다.

---

Search 

https://bcp0109.tistory.com/57

https://deok2kim.tistory.com/101