[BOJ] 2240번 : 자두나무

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int t, w; 
int d[1005][32][3]; 
int cherry[1005];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> t >> w; 
	for (int i = 1; i <= t; i++) cin >> cherry[i]; 

	for (int i = 1; i <= t; i++) {
		d[i][0][1] = d[i - 1][0][1] + (cherry[i] == 1 ? 1 : 0); 

		for (int j = 1; j <= w; j++) {
			if (cherry[i] == 1) {
				d[i][j][1] = max(d[i - 1][j - 1][2], d[i - 1][j][1]) + 1; 
				d[i][j][2] = max(d[i - 1][j][2], d[i - 1][j - 1][1]);
			}
			else {
				d[i][j][1] = max(d[i - 1][j - 1][2], d[i - 1][j][1]);
				d[i][j][2] = max(d[i - 1][j][2], d[i - 1][j - 1][1]) + 1;
			}
		}
	}
	int ans = 0; 
	for (int i = 0; i <= w; i++) {
		ans = max(ans, d[t][i][1]);
		ans = max(ans, d[t][i][2]);
	}
	cout << ans << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x10.md

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

dp를 이용해 풀어야 한다. 따라서, 세 가지 스텝으로 문제를 푼다. 

1. 테이블정의 

d [i][j][k] --> 시간이 i, 이동 횟수 j , 나무의 위치 k 일 때, 먹을 수 있는 자두의 최댓값으로 정의한다. 

 

2. 점화식 

first. 움직이지 않는 경우, 즉, 이동 횟수가 0이고, 1번 트리에만 있는 경우, 

d [i][0][1] = d [i-1][0][1] + (cherry [i] == 1? 1 : 0 ) 

 

second 움직이는 경우, 

second.1. 떨어지는 체리가 1번 트리인 경우, 

d [i][mv][1] = max(d [i-1][mv-1][2] , d [i-1][mv][1]) + 1; 

d [i][mv][2] = max(d [i-1][mv][2], d [i-1][mv-1][1]) --> 체리를 먹지 않고, 다른 트리로 이동 

 

second.2. 떨어지는 체리가 2번 트리인 경우, 

d [i][mv][1] = max(d [i-1][mv-1][2] , d [i-1][mv][1]) ; --> 체리를 먹지 않고, 다른 트리로 이동

d [i][mv][2] = max(d [i-1][mv][2], d [i-1][mv-1][1]) + 1; 

 

3. 초기값 설정 

초기값은 d [0][0~w][1~2]를 0으로 설정한다.