백준 2758번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	골드 4

사진을 클릭하면 문제로 이동합니다.

---

풀이

 맨 처음엔 백트래킹으로 접근했지만, 점점 개선하다보니 dp였던 문제.

 

 각 자릿수는 이전 자릿수의 2배여야 하기에, 각 자리에 올 수 있는 숫자의 최댓값은 정해져있다. n=4, m=17이라고 하면 각 자리에 올 수 있는 최댓값은 각각 2,4,8,17이다. 이 최댓값들까지 각 숫자들을 재귀를 이용해 순회하면서 개수를 찾아준다. 같은 예제를 기준으로 설명하면, 맨 처음 숫자는 1부터 2까지 순회하며, 재귀를 통해 각 숫자의 2배만큼의 숫자와, 남은 결정해야하는 숫자를 넘겨준다. f(2, 3)과 같은 식으로 말이다.

 

 하지만 여기서 TLE에 대한 문제가 발생한다. 1 4 8 16과 2 4 8 16을 보면 둘다 n=4, m=17이라는 예제에 부합하면서, 4 이후로 반복되는 것을 볼 수 있다. 지금이야 숫자가 작으니 상관 없지만, 숫자가 커진다면 같은 연산을 여러번 반복할 것이고, 이는 시간제한에 통과하지 못 할수 있다. 이럴때 우리가 무엇을 사용했던가? 메모이제이션이다. 어떤 숫자 n이 k번째에 등장했을 때, 이 이후로 5개의 조합이 존재한다는 것을 첫 연산때 알았다면, memo[n][k]에 5를 저장하여, 이후에 또 등장한다면 memo의 값을 통해 바로 연산하고 끝낼 수 있을 것이다. 이때 숫자가 커질수 있기 때문에 메모이제이션의 값은 long long으로 처리하는게 안전할 것이다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

int n, m;
ll memo[10][2001];

ll sol(int cnt, int cur) {
	if (memo[cnt][cur] != -1) {
		return memo[cnt][cur];
	}

	if (cnt == 0) {
		return m - cur + 1;
	}

	memo[cnt][cur] = 0;
	for(int i = cur; i <= m / (1 << cnt); i++) {
		memo[cnt][cur] += sol(cnt - 1, i * 2);
	}
	return memo[cnt][cur];
}

int main() {
	cin.tie(0)->sync_with_stdio(false);

	int tc; cin >> tc;
	
	while(tc--) {
		cin >> n >> m;
		for(auto& row : memo) memset(row, 0xff, sizeof(ll)*2001);
		cout << sol(n - 1, 1) << endl;
	}
}