백준 1351 c++ "무한 수열" -PlusUltraCode-

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

 

[필자 사고]

문제에서 N의 범위가 10^12승이다 일반적인 방법으로 배열을 선언시 시간초과가 난다.

그렇다면 맵이나 set을 이용해서 원하는 값만 넣고 값을 찾느 ㄴ형태로 구현해야 된다는 사고과정이 흘렀다.

또한 저 값들을 N에서 부터 시작하여 백트래킹 즉 탑 다운 방식으로 문제를 해결할 수 있따는 아이디어도 떠올려 졌다.

 

위 두 가지 사고과정이 생기게 되면 해당 문제를 타파할 수 있따.

아래는 자세한 코드해설이다.

[코드 해설]

 

• DFS 함수:
  이 함수는 idx라는 인덱스를 받아 재귀적으로 값을 계산합니다.
  • 만약 idx가 0이라면, 값이 1로 설정되고 종료됩니다.
  • myMap[idx]가 이미 계산되어 있으면 재귀 호출을 하지 않고 값을 반환합니다. 이 부분은 이미 계산된 값을 메모이제이션 (Memoization)하여 효율성을 높이는 부분입니다.
  • 그렇지 않으면 myMap[idx / P]와 myMap[idx / Q]를 참조하여 각각 그 값이 1보다 작으면 해당 인덱스에 대해 재귀적으로 DFS를 호출합니다.
  • 최종적으로 myMap[idx]는 myMap[idx / P] + myMap[idx / Q]의 값을 저장합니다. 이는 특정 인덱스에서의 값이 그 이전 값들의 합으로 정의되는 점화식을 따라 계산됩니다.
• Input 함수:
  이 함수는 N, P, Q 값을 입력받는 함수입니다. 입력 값은 게임 시작에 필요한 변수들로, 문제를 풀기 위해 DFS 함수에서 사용됩니다.
• Game_Start 함수:
  이 함수는 DFS(N)를 호출하여 N에 대한 결과를 계산하고, 그 값을 출력합니다. 이때 myMap[N]은 계산된 결과를 의미합니다.
• main 함수:
  main 함수는 프로그램의 시작점을 정의합니다. 여기서는 먼저 Input 함수를 호출하여 값을 입력받고, 그 후 Game_Start를 호출하여 결과를 계산하고 출력합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <map>
using namespace std;

long N, P, Q;
map<long, long> myMap;


void DFS(long idx) {

	if (idx == 0) {
		myMap[idx] = 1;
		return;
	}
	if (myMap[idx] != 0)return;
	

	long firstValue = myMap[idx/P];
	long secondValue = myMap[idx / Q];
	
	if (firstValue<1) {
		
		DFS(idx / P);
	}
	if (secondValue <1) {
		DFS(idx / Q);
	}
	
	myMap[idx] = myMap[idx / P] + myMap[idx / Q];
}

void Input() {
	cin >> N >> P >> Q;

}

void Game_Start() {
	DFS(N);
	cout << myMap[N];
}

int main(void) {
	Input();
	Game_Start();
}