[BOJ/Gold 5] 백준 2421 저금통(C++)

문제 링크

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

 

문제

홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다.

홍태석은 소수를 좋아하는 것으로 서강대에서 유명하기 때문에, 첫째 저금통에 들어있는 돈의 양과 둘째 저금통의 돈의 양을 이어붙였을 때, 그것이 소수가 되는 것을 너무나도 좋아한다.

예를 들어, 첫째 저금통에 12원이 있고, 둘째 저금통에 7원이 있다고 하자. 그럼 그 두 수를 이은 127은 소수가 된다.

이제, 최대한 소수가 많이 나오도록, 홍태석이 돈을 넣는 최적의 순서를 찾아내면 된다. 가장 처음에 두 저금통에는 1원씩 들어있다.

예를 들어,  N=4일 때를 보자.

1,1 → 2,1 → 2,2 → 3,2 → 3,3 → 4,3 → 4,4

위와같이 돈을 넣으면 소수는 오직 1번 등장한다. (43)

하지만, 다음과 같이 돈을 넣으면 소수는 3번 (31,41,43) 등장하게 된다.

1,1 → 2,1 → 3,1 → 4,1 → 4,2 → 4,3 → 4,4

위의 예가 N=4일 때 의 답이다. 가장 처음에 11은 세지 않는다.

 

입력

첫째 줄에 N이 주어진다. (1<=N<=999)

 

출력

첫째 줄에 소수가 가장 많이 나오는 저금 방법에서 소수가 나오는 횟수를 출력한다.

 

예제 입력 1

4

예제 출력 1

3

 

알고리즘 분류

• 다이나믹 프로그래밍
• 소수 판정

 

풀이

등장할 수 있는 수의 최댓값은 999999이다.(999 + 999)

따라서 2부터 100만까지 에라토스테네스의 체를 활용해서 소수인 수를 기록해둔다.

이제 저금통에 돈을 넣어야 한다. 먼저 두 저금통에는 각각 1원이 들어 있고, 홍태석은 각 저금통마다 1원씩 넣을 수 있다.

두 저금통에 돈이 얼마씩 들어있을 때, 등장할 수 있는 소수의 개수의 최댓값을 기록해야 한다.

DP[i][j]라는 2차원 배열을 선언한다. 이는 첫 번째 저금통에 i원이, 두 번째 저금통에 j원이 들어있을 때 등장할 수 있는 소수의 개수의 최댓값이다.

2차원 반복문으로 (1, 1)부터, 두 저금통의 돈에 따라 달라지는 숫자가 소수인지 아닌지를 판별하고, DP[i][j]의 최댓값을 기록한다.

마지막에 기록된 DP[N][N]이 우리가 구하는, 두 저금통을 N원까지 채웠을 때 등장할 수 있는 소수의 개수의 최댓값이 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MAX 1000
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
int Era[MAX * MAX];
int DP[MAX][MAX];

void init() {
    for (int i = 2; i < (MAX * MAX); i++) {
        Era[i] = i;
    }

    for (int i = 2; i <= sqrt(MAX * MAX); i++) {
        if (Era[i] == 0) continue;
        for (int j = (i * i); j < (MAX * MAX); j += i) {
            Era[j] = 0;
        }
    }
    Era[11] = 0;
}

void input() {
    cin >> N;
}

void settings() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int Number = stoi(to_string(i) + to_string(j));
            if (Era[Number] == 0) {
                DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
            }
            else {
                DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]) + 1;
            }
        }
    }
}

void find_Answer() {
    cout << DP[N][N] << "\n";
}

int main() {    
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}