[백준/BOJ] 9461번 파도반 수열 (C/C++)

백준 온라인 저지(BOJ) 9461번 파도반 수열

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

9461번: 파도반 수열

* 사용언어 : C언어, C++

 

1. 문제

아래 그림과 같이 삼각형들이 나선 모양(시계 방향)으로 놓여져 있음

P(N)은 나선 중 N번째 정삼각형의 변의 길이일 때 P(N)을 출력

 

2. 풀이

수열의 규칙을 찾아 bottom-up 방식으로 구현하여 풀면 됩니다.

초반 삼각형들을 살펴보면 규칙이 잘 안 보이는데 오히려 그림에서 큰 삼각형(7, 9, 12 등)을 보면 규칙이 쉽게 보입니다.

 

9의 경우 인접한 7과 2를 합쳐서 만들어지고, 12의 경우 9와 3을 합쳐서 만들어집니다.

따라서 [n번 정삼각형] 변의 길이는 [n - 1번]과 [n - 5번] 정삼각형의 변의 길이의 합이라는 것을 알 수 있습니다.

 

그렇기 때문에 1부터 5까지는 초기값을 그대로 세팅하고(p[1] = p[2] = p[3] = 1, p[4] = p[5] = 2)

위 규칙에 따라 100번 까지 합을 한 번만 구해놓고서 N에 따라 p[N]을 출력만 해주면 됩니다.

 

 

한 가지 주의할 점은 p[79] 부터 int의 범위(약 -21억 ~ 21억)를 넘기 때문에

배열을 long long으로 선언해주어야 정답이 됩니다.

 

만약 4%에서 틀렸습니다가 나온다면 범위가 틀린 것이니 배열 Type을 수정하면 됩니다.

p[77]가 약 13억, p[78]이 약 18억

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
9461_파도반 수열
1112KB	0ms
*/
#include <cstdio>

const int LM = 101;
long long p[LM];
int T, N;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &T);
	p[1] = p[2] = p[3] = 1;
	p[4] = p[5] = 2;
	for (int i = 6; i < LM; ++i) p[i] = p[i - 1] + p[i - 5];

	while (T--) {
		scanf("%d", &N);
		printf("%lld\n", p[N]);
	}
	return 0;
}

* long long 출력 시 "%d"가 아닌 "%lld"를 사용해야 합니다.