Baekjoon 17291 새끼치기

Link https://www.acmicpc.net/problem/17291

소스결과 1998 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 구현, 다이나믹 프로그래밍

 

설명

벌레가 특정 기준을 기준으로 분열하며 새로운 벌레를 만들어 낼 때 N년후 존재하는 벌레를 출력하자.

 

알고리즘

1. 짝수해 홀수해를 구분하여 벌레의 수를 0으로 줄인다.

2. 0부터 특정 해 까지 살아 남아있는 모든 벌레를 더한다.

 

소스코드

#include <iostream>

using namespace std;

int worms[21] = { 1, 1, 2, 4 };

void init(int n)
{
	for (int j = 4; j <= n; j++)
	{
		for (int i = 0; i < j; i++) {
			//짝수 해
			if (i % 2) {
				if (i + 4 < j)
					worms[i] = 0;
			}
			//홀수 해
			else {
				if (i + 3 < j)
					worms[i] = 0;
			}
		}

		int val = 0;
		for (int i = 0; i < j; i++)
			val += worms[i];

		worms[j] = val;
	}
}

int main()
{
	int n; cin >> n;

	init(n);

	cout << worms[n] << endl;

	return 0;
}