(백준 2240번) 자두나무
문제 설명
자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.
매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.
자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.
입력
첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.
출력
첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.
문제 풀이
다이나믹 프로그래밍을 활용하는 문제이다. 다이나믹 프로그래밍 문제의 경우 현재까지 꽤 많이 풀어봤음에도 여전히 문제에서 요구하는 점화식을 잡는게 쉽지가 않았다. 강의에서 본 대로 메모장에 제일 처음의 경우의 수부터 시작하여 쭉 나열한 후 규칙을 찾아보았던 것이 문제 풀이에 많은 도움이 되었다. 앞으로도 dp 문제를 풀 땐 이렇게 시작해야 할 것 같다.
문제를 풀 때 나는 dp 배열을 dp[초][자리를 바꾼 횟수][자리] 의 3차원 배열로 잡았다. 그리고 매 초마다 자두가 없는 자리는 그 이전 초의 값을 그대로 가져오고, 자두가 있는 자리는 max(dp[이전 초][자리를 바꾼 횟수-1][반대자리]+1,dp[이전 초][자리를 바꾼 횟수][현재자리]+1) 로 현재 초, 현재 자리를 바꾼 횟수, 현재 자리에서의 최대값을 구하였다.
점화식만 구하면 쉽게 풀리는 것은 좋지만 언제나 점화식을 잡는 것이 어려워 더 많은 문제를 풀어서 경험으로 극복해야할 것 같다.
사담으로 처음에 dp배열을 잡을 때에 dp[t+1][w+1][3] 으로 잡았었는데, 분명 배열을 0으로 초기화 했음에도 정답으로 계속 쓰레기 값이 나왔다. 이에 대해 찾아보니 VLA라는 기능의 존재와 그 장단점에 대해 알 수 있었는데, 현재 내가 쓰는 vscode에선 VLA를 제대로 지원하지 않아 생긴 문제같았다. 앞으로 가변 배열이 필요할 땐 vector를 쓰는 버릇을 들여야겠다.
코드
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t, w; cin >> t >> w;
int plum[1005]={0,};
for(int i=1; i<t+1; i++) {
cin >> plum[i];
}
int dyn[1005][35][3]={0,};//dp배열
for(int i=1; i<t+1; i++) {
if(plum[i]==1) {
dyn[i][0][1]=dyn[i-1][0][1]+1;
for(int j=1; j<=w; j+=2) {
dyn[i][j][2]=dyn[i-1][j][2];
}//자두가 없는 자리는 이전값을 그대로 가져옴
for(int j=2; j<=w; j+=2) {
dyn[i][j][1]=max(dyn[i-1][j-1][2]+1,dyn[i-1][j][1]+1);
}//자두가 있는 자리는 이전 시간의 반대자리+1,이전 시간의 현재 자리+1
//중 큰 것을 골라 최대값을 구한다.
}
else if(plum[i]==2) {
for(int j=0; j<=w; j+=2) {
dyn[i][j][1]=dyn[i-1][j][1];
}
for(int j=1; j<=w; j+=2) {
dyn[i][j][2]=max(dyn[i-1][j-1][1]+1,dyn[i-1][j][2]+1);
}
}
}
int maxi=0;
for(int i=0; i<=w; i++) {
for(int j=1; j<3; j++) {
if(dyn[t][i][j]>maxi) maxi=dyn[t][i][j];
}
}//마지막 초 배열의 최대값을 구해 정답을 구한다.
cout << maxi;
}