[BOJ 2695 // C++] 공

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2695번 문제인 공이다.
문제는 아래 링크를 확인하자.

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

2695번: 공

공을 B개 가지고 있고 현재 테스트해봐야 하는 범위에 포함된 층수를 M이라 할 때의 문제의 답을 dp[B][M]이라 하자. 이 때, 이 다음으로 할 수 있는 모든 경우는 B가 2 이상인 경우 1 이상 M 이하의 양의 정수 k에 대하여 공을 범위의 k번째 층에서 떨어뜨렸을 때 공이 어떻게 되는가를 관찰하는 것으로 정리할 수 있다. (B가 1인 경우는 지문에 나와있는 것과 같다.)

 

이 각 경우들 중 이어지는 상황에서 "최악의 경우 공을 던져봐야 하는 횟수"의 최솟값을 구해 그 값에 1을 더한 값을 dp[B][M]의 값으로 해 문제를 해결하자. 1을 더하는 이유는 이번 차례에 공을 한번 던진 것을 구현하는 것이다.

 

이미 구한 값을 다시 구하지 않기 위한 메모이제이션을 이용해 시간복잡도를 감소시켜 문제를 해결하자..

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int dp[51][1001];
bool visited[51][5001];

int func(int B, int M) {
	int& ret = dp[B][M];
	if (!visited[B][M]) {
		visited[B][M] = 1;
		if (B == 1) ret = M;
		else if (M == 0) ret = 0;
		else {
			ret = 1000000007;
			for (int i = 1; i <= M; i++) {
				ret = min(ret, max(func(B, M - i), func(B - 1, i - 1)));
			}
			ret++;
		}
	}
	
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		int B, M; cin >> B >> M;
		cout << func(B, M) << '\n';
	}
}