(2024-11-03) 1 문제 : 백준 - 2560 (짚신벌레)

 

이 문제는 개수를 하나하나 구하기엔 그 개수가 너무 많아서 DP를 이용해 해결하였다.

먼저, DP배열을 통해 각 날짜에 태어나는 짚신벌레의 수만 구해주었다.

 

투포인터를 이용해 (현재 날짜 - b) ~ (현재 날짜 - a) 에 해당하는 DP 누적합을 계속 갱신해주었고 그 값을 DP[현재날짜]에 삽입해주었다. 현재 날짜 - b 일에 태어난 짚신벌레부터 현재 날짜 - a 에 태어난 짚신 벌레들은 현재 날짜에 새로운 개체를 생성할 수 있기 때문이다. 

 

하지만, 태어난 애들 뿐만 아니라 죽은 개체도 고려해야 하는데 이를 고려하기 위해 DP배열에서 (N - d + 1) 부터 N까지의 인덱스에 해당하는 값들만 답으로 추려내주었다. (N - d일 이전에 태어난 개체는 N일 째에 죽어있기 때문)

 

#include <iostream>
#include <vector>
#include <queue>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int StartTime = 0, EndTime = 0, DeathTime = 0, MaxDay = 0;
    std::cin >> StartTime >> EndTime >> DeathTime >> MaxDay;

    std::vector<int> DP(MaxDay + 1);
    
    DP[0] = 1;
    int BirthBug = 0;

    for(int i = 1; i <= MaxDay; i++)
    {
        if (i - StartTime >= 0)
        {
            BirthBug += DP[i - StartTime];
        }

        if (i - EndTime >= 0)
        {
            BirthBug -= DP[i - EndTime];
        }

        DP[i] += BirthBug;
        DP[i] %= 1000;
    }

    int Sum = 0;

    for (int i = std::max(0, MaxDay - DeathTime + 1); i <= MaxDay; i++)
    {
        Sum += DP[i];
        Sum %= 1000;
    }

    std::cout << Sum;

    return 0;
}