[C++] 백준 9461번 파도반 수열

1. 문제이해

9461번: 파도반 수열 (acmicpc.net)

9461번: 파도반 수열

 

그림과 같이 삼각형들이 나선형으로 놓인 도형이 주어진다.

첫 삼각형은 정삼각형이고, 변의 길이가 1이며, 다음과 같은 과정으로 정삼각형이 계속 추가된다.

파도반 수열 P[n]이 n번째 정삼각형의 한 변의 길이를 나타낼 때,

각 테스트 케이스의 P[n] 값을 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

나선형으로 놓인 삼각형들이 다음과 같이 있을 때,

n번째 삼각형의 한 변의 길이를 구하는 것이 목표이다.

삼각형의 한 변의 길이는, 문제에서 주어졌듯이

1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ...

순서대로 수열을 이루고 있다.

 

문제에서 주어진 나선형으로 이루어진 삼각형의 집합은 위와 같다.

여기서, 삼각형 내부의 숫자는 해당 삼각형의 한 변의 길이이다.

 

해당 나선형 삼각형의 집합에서, 삼각형의 순서는 위와 같다.

가장 안쪽의 삼각형부터 시작해, 11번째 삼각형까지 구성되어있다.

 

삼각형의 각 변의 길이와 순서를 잘 숙지하고,

이제 아래 예제를 통해 위와 같은 도형이 어떠한 규칙을 띄고 있는지 알아보자.

 

---

 

<예제 1>

 

한 변의 길이가 4인 7번째 삼각형을 자세히 보자.

해당 삼각형의 한 변의 길이는, 그림과 같이

변의 길이가 1, 3인 삼각형의 합과 같으며,

이는 각각 2(7-5)번째, 6(7-1)번째 삼각형과 같다.

 

 

<예제 2>

 

한 변의 길이가 9인 10번째 삼각형을 자세히 보자.

해당 삼각형의 한 변의 길이는, 그림과 같이

변의 길이가 2, 7인 삼각형의 합과 같으며,

이는 각각 5(10-5)번째, 9(10-1)번째 삼각형과 같다.

 

---

 

위의 예제를 통해,

N번째 삼각형의 한 변의 길이 = (N-5)번째 삼각형의 길이 + (N-1)번째 삼각형의 길이

와 같은 규칙이 나타나는 것을 알 수 있다.

알아낸 해당 규칙을 통해 코드를 구현하면 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

// int형 사용시 범위를 넘어가게 되어 long long 형 사용
long long spiral_triangle(int n) {
	long long P[101];
	P[0] = 1;
	P[1] = 1;
	P[2] = 1;
	P[3] = 2;
	P[4] = 2;

	for (int i = 5; i < n; i++) {
		P[i] = P[i - 1] + P[i - 5];
	}

	// 첫번째 삼각형이 수열 P[0]부터 해당하므로 -1
	return P[n - 1];
}

int main() {
	int T;
	int num;

	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> num;
		cout << spiral_triangle(num) << endl;
	}

	return 0;
}

spiral_triangle 이라는 함수를 두어, 위 문제풀이 과정에서 알아낸 풀이방식을 따로 구현했다.

(int 형으로 구현 시, 범위를 초과하게 되므로, long long 형 사용)

 

P[0] ( = 1번째 삼각형의 변의 길이)부터 P[4] ( = 5번째 삼각형의 변의 길이)까지,

삼각형의 한 변의 길이를 저장하고,

for문을 통해 P[5] ( = 6번째 삼각형의 변의 길이) 부터는 규칙을 적용했다.

(N번째 삼각형의 한 변의 길이 = (N-5)번째 삼각형의 길이 + (N-1)번째 삼각형의 길이)

이후, P[n-1] 값을 리턴하게 되는데, P[0]이 1번째 삼각형부터 시작하므로, -1을 해주었다.

 

메인 함수에서는 테스트 케이스의 개수와 해당 개수만큼

num(num번 째 삼각형의 한 변의 길이)을 입력받고, spiral_triangle함수의 인자로 건넨다.

num은 위와 같은 과정을 거쳐 P[num - 1] 값을 출력하게 된다.

 

 

---

다이나믹 프로그래밍은 규칙을 잘 알아내는게 정말 중요한 것 같다.😌

더 여러운 프로그래밍 문제도 많이 도전해봐야지..