[BOJ] 새끼치기(17291)

[백준(BOJ)] 새끼치기(17291) C++

문제 : BOJ_17291번 새끼치기

문제 설명

위상정렬, DP(다이나믹 프로그래밍)

1년에 한 마리였던 벌레가 매년 분열하고
1)홀수 연도에 분열했던 벌레는 3번 분열 시 사망
2)짝수 연도에 분열했던 벌레는 4번 분열시 사망

임으로, 해당 년도에 살아있는 벌레들이 언제 분열했는지를 저장해야 됨으로 2중 dp를 통해 풀 수 있습니다.

---

Solution

이중 배열을

dp[현재 연도][태어난 연도] = 벌레 수

로 정해서 풀어봅시다. 2중 포문을 통해 매년마다

dp[현재 연도][현재 연도] = dp[현재 연도-1][태어난 연도]
로 분열된 벌레를 저장해준다.

기존에 남아있던 벌레는 홀수 3년, 짝수 4년 안에 분열된 벌레라면

dp[현재 연도][분열된 연도] = dp[현재 연도-1][태어난 연도]

로 저장해줍니다.

---

Description

기존에 남아있는 벌레를 새로운 연도에 저장할 때 조건문을 주의해서 짜도록 해야 합니다.

#include <iostream>
using namespace std;
int dp[21][21]; // dp[현재 연도][태어난 연도] = 벌레 수
int main(void) {
    dp[1][1] = 1;
    for (int i = 2; i <= 20; i++) {
        for (int j = 1; j < i; j++) {
            if (j % 2) { // 홀수 연도에 태어난 벌레
                if (i - j < 3) dp[i][j] += dp[i - 1][j];
            }
            else if (i - j < 4) dp[i][j] += dp[i - 1][j]; // 짝수 연도에 태어난 벌레
            dp[i][i] += dp[i - 1][j]; // 현재 연도에 태어난 벌레
        }
    }
    int year;
    scanf("%d", &year);
    int result = 0;
    for (int i = 1; i <= year; i++) result += dp[year][i];
    printf("%d\n", result);
}