[cpp 알고리즘] 백준 17291 새끼치기

[백준] 17291 새끼치기 cpp 풀이

알고리즘: 구현, 다이나믹 프로그래밍(DP)

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

문제 요약

아래의 벌레 분열 규칙만 고려해서 코드를 풀이하면 된다. 

 

1. 벌레는 기준년도 1년 2월에 1마리가 탄생한다.
2. 벌레는 매년 1월이 되면 분열한다. 분열시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다.
3. 홀수년도에 탄생한 개체는 3번 분열시, 짝수년도에 탄생한 개체는 4번 분열시 사망한다.

이 때, N년 말에 존재하는 벌레의 수를 구하면 된다. 

풀이 정리

- 기준년도 1년 2월 = 1 마리

- 2년 1월 = 1 + 1(새로 분열)

- 3년 1월 = 1 + 1 + 2(새로 분열)

- 4년 1월 = 1 + 1 + 2 + 4(새로 분열) - 1(기준년도 1년 벌레 사망)

- 5년 1월 = 0 + 1 + 2 + 4 + 7(새로 분열)

- 6년 1월 = 0 + 1 + 2 + 4 + 7 + 14(새로 분열) - 1(2년 벌레 사망) - 2(3년 벌레 사망)

- 7년 1월 = 0 + 0 + 0 + 4 + 7 + 14 + 25

 

한 번 하다보면, 이런 식으로 진행되는 것을 알 수 있고,

(1) 매년도마다 전년도의 벌레 합 만큼 새로 분열되고, (2) 짝수년도마다 각각 3년 전, 4년 전 벌레들은 사망한다. 

DP를 이용해서 dp[n]= n번 째에 살아있는 벌레 마리 수 로 풀었다. 

 

C++ 코드

#include <iostream>
using namespace std;

int N;
int arr[21];

int main(){
    cin >> N;
    
    for(int i=1; i<=N; i++){
        if(i==1) arr[i] = 1;
        else if(i==2) arr[i] = 1;
        else if(i==3) arr[i] = 2;
        else{
            int sum=0;
            for(int j=1; j<=i; j++) sum+= arr[j];
            arr[i] = sum;
            
            if(i%2==0){
                int tmp1 = i-3;
                int tmp2 = i-4;
                
                if(tmp1>=0) arr[tmp1] = 0;
                if(tmp2>=0) arr[tmp2] = 0;
            }
        }
    }
    
    int ans=0;
    for(int i=1; i<=N; i++) ans+=arr[i];
    cout << ans;
    return 0;
}

 

DP를 더 활용한 C++ 코드

정말 간단하게 한다면, 아래와 같이 할 수도 있다. 

for (int i = 2; i <= N; ++i)
	dp[i] = dp[i - 1] * 2 - (i % 2 ? 0 : dp[i - 4] + dp[i - 5]);