[C++] 백준 9507번 Generations of Tribbles

1. 문제이해

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

9507번: Generations of Tribbles

 

다음과 같은 피보나치 함수를 koong(n) (꿍 피보나치) 라고 할 때,

입력받은 n번째 꿍 피보나치를 출력하는 프로그램을 만드는 것이 목표이다.

n < 2 :                         1
n = 2 :                         2
n = 3 :                         4
n > 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4)

 

 

 

2. 문제풀이

 

간단한 DP문제이다.

사실 친절하게 수식까지 다 세워줘서 딱히 풀이라고 쓸 만한 것도 없는 것 같다..

그렇다고 그냥 넘어가기는 아쉬우니, DP(Dynamic Programming)의 개념에 대해 다시 한번 짚고 넘어가자.

 

Dynamic Programming, 일명 DP란, 말 그대로 동적 계획법이다.

소위 큰 문제를 나누어 작은 문제들로 나누어 푸는 것으로,

하나의 문제는 한번만 풀도록 하는 알고리즘으로 볼 수 있겠다.

분할정복과 비슷하게 느껴질 수도 있으나, 분할정복은 하나의 문제를 여러번에 걸쳐서 푼다는 차이점이 있다.

 

이번 문제처럼 가장 대표적인 DP 문제는 피보나치 수열이다.

피보나치 수열이란, 특정 숫자를 구하기 위해 이전 숫자와 그 이전의 숫자를 더하는 수열로,

식으로 나타내면 다음과 같다.

 

fibonacci [ i ] = fibonacci [ i - 1 ] + fibonacci [ i - 2]

출처 : 삼성디스플레이 뉴스룸

 

 

이번 문제에서의 꿍 피보나치는 위 피보나치 수열을 살짝 변형한 것 뿐이다.

식도 친절하게 주어져있으니, 나머지는 코드로 그대로 구현만 하면 된다.

더 많은 DP문제와 해당 풀이는 아래 링크를 참고하자.

(혹은 포스팅 하단의 다이나믹 프로그래밍 태그를 클릭)

 

https://beginnerdeveloper-lit.tistory.com/tag/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D

초보 개발자의 이야기, 릿허브

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

int main() {
	int t;	// 테스트 케이스
	int input;
	long long koong[68];

	cin >> t;

	koong[0] = 1;
	koong[1] = 1;
	koong[2] = 2;
	koong[3] = 4;

	// 꿍 피보나치 계산
	// n > 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4)
	for (int i = 4; i < 68; i++) {
		koong[i] = koong[i - 1] + koong[i - 2] + koong[i - 3] + koong[i - 4];
	}

	// t번째 꿍 피보나치 출력
	for (int i = 0; i < t; i++) {
		cin >> input;
		cout << koong[input] << "\n";
	}

	return 0;
}

테스트 케이스 t를 입력받고, 꿍 피보나치(koong)를 계산한다.

값과 수식은 문제에서 주어진 것과 동일하다.

이후, for문을 통해 각 테스트케이스에서의 꿍 피보나치를 출력한다.

 

 

---