백준 9461 - 파도반 수열

www.acmicpc.net/problem/9461

9461번: 파도반 수열

그려보면서 일반화했는데, 틀렸다고 나와서 예외를 찾느라 시간을 소모했다. integer 범위를 넘어가서 문제가 생긴걸 확인하곤 고쳐서 금방 풀었다.

 

문제)

 나선 모양으로 놓인 삼각형의 변의 길이를 구하여라. 놓인 삼각형 중 가장 긴 변에 그 변의 길이를 한 변의 길이로 하는 삼각형을 놓는다.

(1<=N<=100)

 

풀이)

 DP로 풀면 된다. 단, dp[99]까지 출력해보면 알겠지만 integer 표현범위를 넘어간다. 따라서 long long (int)를 사용하여야 오버플로 발생을 막을 수 있다.

 

C 코드)

#include <stdio.h>

int N, T;
long long int dp[100];

int main() {
	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 1;
	dp[3] = 2;
	dp[4] = 2;
	for(int i=5;i<100;i++) {
		dp[i] = dp[i-5] + dp[i-1];
	}
	scanf("%d", &T);
	for(int i=0;i<T;i++) {
		scanf("%d", &N);
		printf("%lld\n", dp[N-1]);
	}
}