[백준] 9461-파도반 수열

쉬운 dp 문제입니다.

그림을 보시면 삼각형들은 2면을 맞닿으며 규칙적인 모양을 가지는 것을 확인 할 수 있습니다.

P(1)부터 P(11)까지 첫 11개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16 ... 

 dp[n] = dp[n-1] + dp[n-5] 라는 점화식을 찾을 수 있게 됩니다.

정답률이 30%대라는게 믿기지 않을 정도로 쉬워서 의아하며, 

ㅋㅋㅋㅋㅋㅋㅋㅋ

한번 틀렸습니다. 숫자가 증가함에 따라 기하급수적으로 수가 커지는거를 신경못썻습니다. 

int형은 4byte = 32bit = 2의 32승

즉 2,147,483,648x2 만큼의 수를 저장할 수 있습니다.

음수,0양수 모두를 포함해야하기 때문에 아래 표와 같은 범위의 수를 표현할 수 있게 됩니다.

수가 넘어갈때는 제일 아래의 음수값 - 2,147,483,648로 내려가 1씩 올라가며 출력을 하는 구조입니다.

저는 c++에서 long long 형을 사용하여 문제를 해결하였습니다. 

정답코드

#include <iostream>
using namespace std;

long long dp[101] = { 0 };
int t = 0, n;
int main() {
	dp[1] = 1, dp[2] = 1, dp[3] = 1, dp[4] = 2;
	for (int i = 5; i <= 100; i++)
		dp[i] = dp[i - 1] + dp[i - 5];

	cin >> t;

	while (t--) {
		cin >> n;
		cout << dp[n] << endl;
	}
}