백준 15988 c++ "1, 2, 3 더하기 3" -PlusUltraCode-

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

 

 

[필자 사고]

점화식을 세우기 쉬운 dp문제이다.

주목해야 될 숫자들은 1, 2,3, 이다.

계단식 문제와 같은 풀이를 진행해주면 쉽게 풀 수 있다.

상세한 내용은 아래에 적어 놓겠다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

[코드 해설]

1. 동적 계획법 (DP) 배열 초기화 (Make_DP 함수)

Make_DP 함수는 최대 1,000,000까지의 정수를 다룰 수 있도록 DP 배열을 초기화하는 역할을 한다.

• dp 벡터를 크기 1,000,001로 설정한다.
• 점화식 기반으로 DP 배열을 채운다.
  • dp[1] = 1 → 1을 만드는 방법: {1}
  • dp[2] = 2 → 2를 만드는 방법: {1+1, 2}
  • dp[3] = 4 → 3을 만드는 방법: {1+1+1, 1+2, 2+1, 3}
  • dp[n] = dp[n-1] + dp[n-2] + dp[n-3]을 사용하여 n까지 계산
  • 매 연산마다 1000000009로 나머지를 구해 값이 너무 커지는 것을 방지한다.

2. 입력 처리 (Game_Start 함수)

Game_Start 함수는 입력값 N을 받아 해당하는 DP 결과값을 출력하는 역할을 한다.

• cin을 통해 N 값을 입력받는다.
• dp[N] 값을 출력한다.

3. 프로그램 실행 (main 함수)

• T(테스트 케이스 개수)를 입력받는다.
• Make_DP()를 호출하여 DP 테이블을 초기화한다.
• T번 반복하며 Game_Start() 함수를 실행한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<long> dp;
int N;

void Make_DP() {
	dp.resize(1000001);
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	
	for (int i = 4; i <= 1000000; i++) {
		dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
		dp[i] %= 1000000009;
	}
}

void Game_Start() {
	cin >> N;
	cout << dp[N] << '\n';
	
}

int main(void) {
	int T;
	cin >> T;
	Make_DP();
	while (T--) {
		Game_Start();
	}
}