백준 16400 소수 화폐

백준 16400 소수화폐

---

오늘은 소수화폐 문제를 풀었는데, 에라토스테네스를 이용해 소수를 구한 후 이를 이용해 dp 문제를 풀면 되었다.

동전 dp 문제를 오랜만에 풀었더니 기억이 잘 안나서 시간이 오래걸렸다. (알고리즘 문제 자체가 좀 오랜만인것 같기도 하고...)

우선 에라토스테네스로 소수를 구하는 방법이다.

    for (int i = 0; i<= 40000; i++)
    {
        visited[i] = true;
    }
    for (int i = 2; i <= 200; i++)
    {
        for (int j = i*2; j <= 40000; j+=i)
        {
            visited[j] = false;
        }
    }
    for (int i = 2; i<= 40000; i++)
    {
        if(visited[i] == true)
        {
            prime_list.push_back(i);
        }
    }

좀 긴데, 그래도 이게 외우기 제일 쉬워서 이걸로 하게 된 거 같다.

이제 이 소수들로 동전 dp 를 돌리기만 하면 된다.

    cin>>n;    
    for (int i = 0 ; i< prime_list.size(); i++)
    {
        for (int j = prime_list[i]; j <=n; j++)
        {
            dp[j] = (dp[j] + dp[j- prime_list[i]])%123456789;
            dp[j]%= 123456789;
        }
    }

• 2부터 시작하여 dp[j] 에 dp[i] (소수) 를 뺀거 개수를 계속 추가해준다.
• 예를 들어 dp[8] 에는
  • dp[8] = dp[8] + dp[6]
  • dp[8] = dp]8] + dp[5]
  • dp[8] = dp[8] + dp[3]

이렇게 값이 저장되는 것!!