[99클럽/코딩테스트 챌린지/C++] 파도반 수열 문제 해결 및 점화식 구현

문제 링크 :

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

📝 문제 요약

문제: 삼각형이 나선 모양으로 배치된 파도반 수열에서, 주어진 N번째 숫자를 구하는 문제.

입력:

• 테스트 케이스의 개수 T (1 ≤ T ≤ 100)
• 각 테스트 케이스에서 N (1 ≤ N ≤ 100)

출력: 각 테스트 케이스마다 P(N) 출력.

📌 접근법

1. 파도반 수열의 정의

• 점화식: P(N) = P(N-3) + P(N-2) (단, N > 3)
• 초기값: P(1) = 1, P(2) = 1, P(3) = 1
• 첫 몇 개의 값은 다음과 같습니다:

P(1) = 1, P(2) = 1, P(3) = 1, P(4) = 2, P(5) = 2, P(6) = 3, P(7) = 4, ...

 

2. 사전 계산 (Dynamic Programming)

• 점화식을 사용해 P(1)부터 P(100)까지의 값을 한 번만 계산해 저장.
• 각 테스트 케이스에서 미리 계산된 값을 빠르게 출력.

3. 자료형 문제

• P(100)의 값은 int 범위를 초과할 가능성이 있으므로 long long 자료형을 사용.

📌 전체 코드

#include <iostream>
#include <vector>

using namespace std;


int main() {

	int T = 0;
	std::cin >> T;
	vector<long long> dp = vector<long long>(105, 0);
	dp[1] = 1;
	dp[2] = 1;
	for (int i = 3; i < 105; i++)
	{
		dp[i] = dp[i - 3] + dp[i - 2];
	}

	while (T > 0)
	{
		T--;
		int N = 0;
		std::cin >> N;
		std::cout << dp[N] << '\n';
	}

	return 0;
}

📌 배운 점

1, 점화식의 중요성: 파도반 수열의 규칙을 점화식으로 정의하여 문제를 효율적으로 해결할 수 있었습니다.

2, 사전 계산의 효율성: P(100)까지의 값을 미리 계산함으로써, 각 테스트 케이스에서 즉시 결과를 출력할 수 있었습니다.

3, 자료형 선택의 중요성: 문제에서 N이 최대 100까지 주어졌기 때문에, 값이 커질 가능성을 고려하여 long long 자료형을 사용했습니다.

4, 최적화된 코드 작성:

• 동적 계획법(DP)을 사용하여 O(N) 시간 복잡도로 결과를 계산했습니다.
• 테스트 케이스마다 반복 계산을 하지 않고, 한 번의 사전 계산으로 문제를 해결했습니다.

📌 느낀 점

이번 문제를 통해 점화식을 활용한 동적 계획법 문제를 다시 복습할 수 있었습니다. 특히, 자료형 범위를 사전에 고려하는 것이 중요하다는 점을 다시 한번 깨달았습니다. 앞으로도 입력 범위와 자료형을 주의 깊게 분석하여 효율적이고 정확한 코드를 작성해야겠다고 느꼈습니다. 😊