방과후
ALGORITHM NOTE약 2분

BOJ 2240 - 자두나무

자두 다 먹어버리자

#algorithm#boj#gold#dynamic-programming#dp#top-down#memoization
아카이브로 돌아가기

문제 링크

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1<=T<=1,000)초 동안 떨어지게 된다. 자두는 최대 W(1<=W<=30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

풀이

이 문제는 시간과 지금까지 움직인 횟수를 상태로 두는 DP로 풀 수 있다. 현재 시각을 time, 지금까지 이동한 횟수를 cnt라고 하면, cnt의 홀짝에 따라 지금 어느 나무 아래에 서 있는지가 결정된다. 시작이 1번 나무이므로 cnt가 짝수면 1번, 홀수면 2번 나무에 있다.

탑다운 방식에서는 solve(time, cnt)를 "time초부터 끝까지 진행했을 때 받을 수 있는 자두의 최대 개수"로 정의하면 된다. 여기서 매 시점마다 선택지는 두 가지다.

  • 현재 나무에 그대로 있는 경우
  • 아직 이동 가능 횟수가 남아 있다면 반대편 나무로 이동하는 경우

각 선택에서 이번 초에 떨어지는 자두를 받을 수 있는지 계산해 값을 더하고, 두 경우 중 더 큰 값을 메모이제이션한다. 사용자가 설명한 것처럼 "받을 나무를 바꿀지, 바꾸지 않을지"를 계속 분기하며 값을 구하고, 재귀는 가장 끝 시점까지 내려간 뒤 저장된 값들을 이용해 위로 올라오면서 최댓값을 채운다.

stay = solve(time + 1, cnt)는 그대로 있는 경우이고, move = solve(time + 1, cnt + 1)는 이동하는 경우다. 각각 현재 위치 또는 이동한 위치와 tree[time]이 같은지 확인해 1개를 더해주고, 마지막에 max(stay, move)를 반환한다. dp[time][cnt]가 이미 계산됐다면 즉시 반환하므로 중복 재귀를 막을 수 있다.

코드

cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
int t, w;
int tree[1001];
int dp[1001][31];
 
int solve(int time, int cnt) {	
	if (time == t) 
		return 0;
 
	if (dp[time][cnt] != -1) 
		return dp[time][cnt];
 
	int cur = (cnt % 2 == 0) ? 1 : 2;
	int next = 3 - cur;
 
	int stay = solve(time + 1, cnt) + (cur == tree[time] ? 1 : 0);
 
	int move = 0;
	if (cnt < w)
		move = solve(time + 1, cnt + 1) + (next == tree[time] ? 1 : 0);
	
	return dp[time][cnt] = max(stay, move);
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	cin >> t >> w;
	memset(dp, -1, sizeof(dp));
 
	for (int i = 0; i < t; i++)
		cin >> tree[i];
 
	cout << solve(0, 0) << '\n';
	return 0;
}

복잡도

  • 시간 복잡도: O(T⋅W)O(T \cdot W)
  • 공간 복잡도: O(T⋅W)O(T \cdot W)

마무리

이동 여부를 매 초마다 선택해야 해서 브루트포스처럼 보이지만, 상태를 시간과 이동 횟수로 압축하면 깔끔한 DP가 된다. 특히 현재 위치가 cnt의 홀짝으로 바로 정해진다는 점을 이용하면 별도의 위치 차원 없이도 탑다운 메모이제이션을 구현할 수 있다.