[ 백준 / 4811 ] 알약 (C++)

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

 

난이도 : 골드 5 
알고리즘 유형 : DP 
풀이 시간 : 29분 

문제 풀이 

종수 할아버지는 매일 약 반 알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

종수는 2N일동안 약을 먹을 수 있는데, 약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다. 

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H를 보낸다. 총 2N일이 지난 뒤, 만들어질 수 있는 서로 다른 문자열의 개수를 구하여라

 

해당 문제는 경우의 수를 구하는 문제이다. 문제를 읽어보면 알약 한 개를 꺼내서 먹거나, 반 개를 꺼내서 먹거나의 경우가 존재한다. 또한, 문자열의 개수를 구하는 문제이기 때문에, 굳이 문자열을 만들어 볼 필요 없이 top-down DP 알고리즘을 활용해 풀어낼 수 있다.

 

먼저 DP에 사용될 2차원 배열을 생성해 줄 것이다. 여기서 배열의 열은 한 조각을 꺼낸 경우를 저장할 것이고, 행은 반 조각을 꺼낸 경우를 저장할 것이다.

 

이후, top-down 알고리즘을 적용할 것이다. 여기서 제약 사항이 있다.

1. 반 조각의 개수가 한 조각을 선택한 개수보다 많아지면 안된다.

2. 한 조각을 선택한 개수가 N개를 넘어가면 안된다.

 

이 두 조건에 부합할 경우, 약을 선택할 수 없는 경우이기 때문에 0을 리턴해준다. 

 

2N일동안 약을 모두 잘 먹은 경우는 w와 h의 합이 2 * N과 같아지는 경우이다. 이 경우에는 경우의 수가 완성되었기 때문에 1을 리턴해준다.

 

마지막으로 메모이제이션을 적용해주어 이전에 방문했던 조건이라면 바로 dp테이블의 값을 리턴해주도록 설정하여 시간 효율을 증가시켰다.

 

해당 문제의 시간복잡도는 $O(n^2)$이지만 메모이제이션으로 최적화되어있기 때문에 시간 효율이 개선된다.

 

코드

/*
매일매일 약 반알을 먹는다.
한조각을 꺼낸 날에는 W를, 반조각을 꺼낸 날에는 H를 보낸다. 
총 2N일이 지나면 길이가 2N인 문자열이 만들어진다. 이 때, 가능한 서로다른 문자열의 개수는 총 몇 개일까 ?

풀이 : DP

top-down 2차원 배열로 경우의수 찾기
한알짜리 먹는건 행 증가, 반알짜리 먹는건 열 증가
*/

#include <iostream>
#include <cstring>
#define lli long long int

using namespace std;

int t, n;
lli dp[31][31];

lli top_down(int w, int h) {
	if (h > w || w > n)
		return 0;
	if (w + h == 2 * n)
		return 1;
	if (dp[w][h] != -1)
		return dp[w][h];
	dp[w][h] = top_down(w + 1, h) + top_down(w, h + 1);

	return dp[w][h];
}

int main() {
	while (1) {
		cin >> n;
		if (!n)
			break;
		memset(dp, -1, sizeof(dp));

		cout << top_down(0, 0) << '\n';
	}
	
	return 0;
}

배운 점 

문제를 풀며 간단한 점화식 찾는 문제인 줄 알고 뻘짓을 진행했다.

일단 DP 문제란 걸 알았으면 결국 어떤 방법으로든 풀리기 때문에 빠르게 문제의 요지를 잘 파악하는 것이 중요할 것 같다.