★ [2] 124 나라의 숫자 (dp, 재귀)

문제 설명
124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.
124 나라에는 자연수만 존재합니다.
124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.
10진법 124 나라 10진법 124 나라
1 1 6 14
2 2 7 21
3 4 8 22
4 11 9 24
5 12 10 41
자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한사항
n은 50,000,000이하의 자연수 입니다.

입출력 예
n result
1 1
2 2
3 4
4 11

 

---

문제 풀이

처음에 생각없이 무슨 3진법인줄 알고 헤매었다.

정신차리고 노트에 적어가며 툴어보니 dp 문제였다.

근데 효율성 테스트에서 시간초과...

using namespace std;

unordered_map<int, string> dp;
string solution(int n) {
	string answer = "";

	dp[0] = "4";
	dp[1] = "1";
	dp[2] = "2";
	dp[3] = "4";

	if (n < 4)
		return dp[n];

	for (int i = 4; i <= n; i++)
		dp[i] = dp[(i - 1) / 3] + dp[i % 3];

	return dp[n];
}

 

결국 GPT의 힘을 빌려 해답 참조..

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<int, string> dp;

string solve(int n) {
	if (dp.count(n)) return dp[n];

	if (n < 4) return vector<string>{"4", "1", "2", "4"} [n] ;

	return dp[n] = solve((n - 1) / 3) + solve(n % 3);
}

string solution(int n) {
	return solve(n);
}

 

동일한 dp..

결정적인 차이는 나는 dp의 모든 원소를 채우면서 문자열 덧셈 연산을 최대 횟수만큼 해버린것..

* dp.count(n) 는 n이라는 Key 가 있는지 검

1. vector는 O(n log_3(n)) vs unordered_map은 O(log_3(n))

• vector 사용
  • dp[4] ~ dp[n]을 모두 순차적으로 계산해야 함 → 반드시 n번 루프 실행
  • dp[i] = dp[(i - 1) / 3] + dp[i % 3]; 이므로 O(n log_3(n)) 문자열 연산 발생
  • n = 50,000,000이면 굉장히 많은 문자열 연산 필요 → 속도 느림
• unordered_map 사용
  • solve(n)을 호출할 때 필요한 값만 계산 (이미 저장된 값은 재사용)
  • 재귀 호출을 활용하므로 최대 log_3(n)번만 문자열 덧셈이 발생
  • O(n log_3(n)) → O(log_3(n))으로 최적화됨

결국 unordered_map 은 필요한 dp만 구하기 때문에 횟수가 훨씬 줄어든다.

 

dp로 끝나는 것이 아닌, 필요한 원소만 계산할 수 있는 방법을 떠올려라..!!!