[백준 2240] 자두나무

문제 링크 => 2240번: 자두나무 (acmicpc.net)

2240번: 자두나무

---

다이나믹 프로그래밍 문제이다.

 

3차원 배열 dp[x][y][z] 를 설정하였다. (x : 자두의 위치, y : 자두가 떨어지는 초 단위, z : 자두의 움직일 수 있는 횟수)

 

이때 주의깊게 볼 점은 z = 1 일때 움직이는 횟수를 0으로 보는것이 핵심이다. (0으로 볼 경우 배열의 index가 -1을 침범하는 경우가 발생하기 때문)

 

처음의 자두의 위치가 1이라고 주어질 때, 자두가 떨어질 위치가 1, 2일때의 경우를 살펴보자. 

 

위치 1 => 이때의 dp[1][y][z], dp[2][y][z] 값을 다음과 같이 설정할 수 있다.

• dp[1][y][z] = max(dp[1][y-1][z] + 1, dp[2][y-1][z-1] + 1)
• dp[2][y][z] = max(dp[1][y-1][z-1], dp[2][y-1][z])

위치 2 => 이때 조심할 점은 처음의 자두의 위치가 1이라고 주어졌으므로 움직이는 횟수가 0일때 즉, z=1인 경우에만 continue 해주고 그 외의 경우 dp[1][y][z], dp[2][y][z] 값을 다음과 같이 설정할 수 있다.

• dp[1][y][z] = max(dp[1][y-1][z], dp[2][y-1][z-1])
• dp[2][y][z] = max(dp[1][y-1][z-1] + 1, dp[2][y-1][z] + 1)

그리고 최종적으로 dp[1][주어진 t값][1~주어진 움직임의 횟수+1] 에서의 Maximum 을 구해주면 정답이다.

 

DP 너무 어렵다!!!!!!!

---

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

int dp[3][1001][33]; 
int arr[1001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t, w;
	cin >> t >> w;
	for (int i = 1; i <= t; i++) {
		cin >> arr[i];
	}

	for (int i = 1; i <= t; i++) {
		for (int j = 1; j <= w+1; j++) {
			if (arr[i] == 1) {
				dp[1][i][j] = max(dp[1][i - 1][j] + 1, dp[2][i - 1][j - 1] + 1);
				dp[2][i][j] = max(dp[1][i - 1][j - 1], dp[2][i - 1][j]);
			}
			else {
				if (i == 1 && j == 1) continue;
				dp[1][i][j] = max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
				dp[2][i][j] = max(dp[1][i - 1][j - 1] + 1, dp[2][i - 1][j] + 1);
			}
		}
	}
	
	int ans = 0;
	for (int i = 1; i <= w + 1; i++) {
		ans = max({ ans,dp[1][t][i],dp[2][t][i] });
	}
	cout << ans;
	
	return 0;
}