백준 9507 c++ "Generations of Tribbles" -PlusUltraCode-

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

 

;'

[필자 사고]

동적 프로그래밍 문제이다.

동적 프로그래밍에서 가장 중요한 점은 점화식을 세우냐 못 세우냐에 따라 풀수 있는지 없는지 갈린다.

이 문제는 점화식 자체를 공유했다.

점화식 대로 문제를 풀게 되면 쉽게 풀리게 된다.

 

[코드 해설]

3. 입력 처리 및 실행 흐름 (Game_Start 함수)

Game_Start() 함수는 프로그램의 핵심 실행 흐름을 담당합니다.

1. 사용자로부터 정수 NNN을 입력받습니다. NNN은 테스트 케이스의 개수를 나타냅니다.
2. dpdpdp 벡터를 크기 68로 설정하고 초기화합니다.
3. Make_Koong()을 호출하여 Koong 수열을 미리 계산합니다.

이렇게 함으로써 같은 값을 반복해서 계산하는 비효율성을 제거하고, 미리 계산된 값을 활용하여 빠른 응답이 가능하도록 합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long


using namespace std;

int N;
vector<ll> dp;

void Make_Koong() {
	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	for (int i = 4; i <= 67; i++) {
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4];
	}
}

void Game_Start() {
	cin >> N;
	dp.resize(68);

	Make_Koong();
	
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		cout << dp[num] << '\n';
	}
}

int main(void) {
	Game_Start();
}