[BOJ][C++] 백준 2421번: 저금통

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)

출력

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

 

풀이

[i, j] 는 무조건 [i-1, j] 나 [i, j-1] 둘 중 한 단계를 거쳐서 온다.

그렇다면 [i,j]는 저 두 경우가 거쳐오면서 가진 소수의 갯수를 가질 것이다

그리고 [i,j]도 소수라면 그 갯수에 1을 더한 값을 가진다.

즉, dp 문제다. 근데 이제 2차원을 곁들인..

 

2차원 벡터 dp를 만들어준다.

dp[i][j] = i와 j를 이어붙인 값이 되기까지 나온 소수의 갯수

이중 for문으로 각 항을 돌면서 직전 단계 두개([i-1,j] [i,j-1])를 비교하면서 dp를 수행하자

두 단계중 더 큰 값을 고르고, 만약 [i,j]가 소수라면 1을 더해준다.

 

그러기 위해서는 해당 항([i,j])이 소수인지 여부를 알아한다.

2차원 벡터 v를 또 만들어줬다.

v[i][j] = i와 j를 이어붙인 값이 소수인가

 

v를 채우려면 i와 j를 이어붙인 값을 구해야한다.

두 수를 문자열로 만들어서 붙여주고 이를 다시 정수로 바꿔주는 함수를 정의했다.

int connectedNum(int a, int b) {
    return stoi(to_string(a) + to_string(b));
}

 

이제 특정 수가 소수인지 여부도 알아야한다. 벡터 하나를 만들자

isPrime[i] : i가 소수인가?

    isPrime.assign(maxValue, true);
    isPrime[1] = false;
    for(int i=2; i*i<=maxValue; i++) {
        if(!isPrime[i]) {
            continue;
        }
        for(int j=i*i; j<=maxValue; j+=i) {
            isPrime[j] = false;
        }
    }

 

참고로 n의 최댓값이 999다

이 경우 999999라는 수까지 소수 여부를 구해놔야 제대로 써먹을 수 있다

isPrime을 n까지만 구하지 않도록 주의하자

    int maxValue = connectedNum(n,n);

 

 

코드

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

vector<bool>isPrime;

int connectedNum(int a, int b) {
    return stoi(to_string(a) + to_string(b));
}

int main() {
    int n;
    cin >> n;
    
    // isPrime[i] : i가 소수인가?
    int maxValue = connectedNum(n,n);
    isPrime.assign(maxValue, true);
    isPrime[1] = false;
    for(int i=2; i*i<=maxValue; i++) {
        if(!isPrime[i]) {
            continue;
        }
        for(int j=i*i; j<=maxValue; j+=i) {
            isPrime[j] = false;
        }
    }
    
    // v[i][j] = i와 j를 이어붙인 값이 소수인가
    vector<vector<bool>>v(n+1, vector<bool>(n+1, false));
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            int num = connectedNum(i, j);
            v[i][j] = isPrime[num];
        }
    }
    
    // dp[i][j] = i와 j를 이어붙인 값이 되기까지 나온 소수의 갯수
    vector<vector<int>>dp(n+1, vector<int>(n+1, 0));
    dp[1][1] = 0;
    for(int i=2; i<=n; i++) { // dp 초기화
        dp[1][i] = dp[1][i-1] + v[1][i];
        dp[i][1] = dp[i-1][1] + v[i][1];
    }
    for(int i=2; i<=n; i++) { // dp
        for(int j=2; j<=n; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + v[i][j];
        }
    }
    
    // 출력
    cout << dp[n][n];
    
    return 0;
}