[BOJ] 2240 - 자두나무

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

2240번: 자두나무

---

[알고리즘풀이]

t[x] : x 초에 떨어지는 자두의 위치. ( 1이면 1번 나무, 2이면 2번 나무 )

dp[x][y][z] : x 초까지 y 번 방향을 전환했고 현재 z 위치에서 최댓값.

( z 가 0일 때 1번 나무, 1일 때 2번 나무라고 정의 )

 

-초기값

dp[x][0][0] : x 초에 0번 방향을 전환했고 1번 나무 위치에서 최댓값.

               = 1번 나무에서 지금까지 떨어진 자두의 수 ( 방향 전환 없으므로 1번 나무에서 계속 있었다. )

 

dp[x][1][1] : x 초에 1번 방향을 전환했고 2번 나무 위치에서 최댓값.

               = ( x - 1 초에서 0번 방향을 전환했고, 1번 나무 위치에서 최댓값 , x - 1 초에서 1번 방향을 전환했고,

                   2번 나 무 위치에서 최대값 ) 중 더 큰 값에 t[x] 가 2라면 + 1을 해준다.

-점화식

dp[x][y][0] = max(dp[x-1][y-1][1], dp[x-1][y][0]) 에 t[x] 가 1이라면 1을 더해준다.

dp[x][y][1] = max(dp[x-1][y-1][0], dp[x-1][y][1]) 에 t[x] 가 2라면 1을 더해준다.

 

#include<iostream>
#include<algorithm>

using namespace std;

int t[1001];
int n, m;
int dp[1001][31][2];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	// 입력
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
	}
	// 초기값
	for (int i = 1; i <= n; i++) {
		dp[i][0][0] = dp[i - 1][0][0];
		dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0]);
		if (t[i] == 1)
			dp[i][0][0]++;
		if (t[i] == 2)
			dp[i][1][1]++;
	}
	// 점화식
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j][0] = max(dp[i - 1][j - 1][1], dp[i - 1][j][0]);
			dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]);
			if (t[i] == 1)
				dp[i][j][0]++;
			else
				dp[i][j][1]++;
		}
	}
	int result = 0;
	for (int j = 0; j <= m; j++)
		for (int k = 0; k < 2; k++)
			if (dp[n][j][k] > result)
				result = dp[n][j][k];
	cout << result;
}

---