백준 2421번 저금통

문제 링크입니다: https://www.acmicpc.net/problem/2421

우선, 에라토스테네스의 체를 이용하여 미리 1,000,000까지의 소수를 계산한 다음에 다이나믹 프로그래밍을 통해 푸는 문제였습니다.

왼쪽 저금통 혹은 오른쪽 저금통에만 동전을 넣으면 되기 때문에 알고리즘은 꽤나 간단했는데 자릿수라는 변수가 있어서 조금 헤맸던 문제였습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

#include <cmath>

using namespace std;

 

const int MAX = 1000000;

 

int N;

int cache[1000][1000]; //왼쪽 저금통, 오른쪽 저금통

 

//minFactor[i] = i의 가장 작은 소인수(i가 소수인 경우 자기 자신)

int minFactor[MAX];

 

//에라토스테네스의 체를 수행하면서 소인수 분해를 위한 정보 저장

void eratosthenes(void)

{

        //1은 항상 예외 처리

        minFactor[0] = minFactor[1] = -1;

        //모든 숫자를 처음에는 소수로 표시

        for (int i = 2; i < MAX; i++)

                 minFactor[i] = i;

        //에라토스테네스의 체를 수행

        int sqrtMAX = int(sqrt(MAX)); //루트 N

        for (int i = 2; i <= sqrtMAX; i++)

                 if (minFactor[i] == i)

                         for (int j = i * i; j < MAX; j += i)

                                 //아직 약수를 본 적 없는 숫자인 경우 i를 써둔다

                                 if (minFactor[j] == j)

                                          minFactor[j] = i;

}

 

int digitNum(int num) //자릿수

{

        int cnt = 0;

        while (num)

        {

                 cnt++;

                 num /= 10;

        }

        return cnt;

}

 

int maxPrimeNum(int leftCoin, int rightCoin)

{

        //기저사례

        if (leftCoin > N || rightCoin > N)

                 return 0;

 

        //왼쪽 저금통과 오른쪽 저금통으로 만든 숫자 계산

        int rightCoinDigit = digitNum(rightCoin); //오른쪽 저금통 동전 자리수

        int leftCoinDigit = rightCoinDigit; //왼쪽 저금통 동전 자릿수

        int copyLeft = leftCoin;

        for (int i = 0; i < leftCoinDigit; i++)

                 copyLeft *= 10;

 

        //N, N 도달시

        if (leftCoin == N && rightCoin == N)

        {

                 //소수라면

                 if (minFactor[copyLeft + rightCoin] == copyLeft + rightCoin)

                         return 1;

                 else

                         return 0;

        }

 

        int &result = cache[leftCoin][rightCoin];

        if (result != -1)

                 return result;

 

        result = 0;

 

        //문제 조건: 11은 세지 않는다

        if (copyLeft + rightCoin != 11  && minFactor[copyLeft + rightCoin] == copyLeft + rightCoin)

                 result++;

 

        //왼쪽 저금통에 동전을 넣거나 오른쪽 저금통에 동전을 넣는다

        result += max(maxPrimeNum(leftCoin + 1, rightCoin), maxPrimeNum(leftCoin, rightCoin + 1));

 

        return result;

}

 

int main(void)

{

        cin >> N;

 

        eratosthenes();

        memset(cache, -1, sizeof(cache));

        cout << maxPrimeNum(1, 1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~