[ boj : 2421 ] 저금통

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

2421번: 저금통

문제 : (1,1)에서 (N,N)이 될때까지 수를 이어붙여서 나올 수 있는 소수의 횟수를 구해라

해설 : 전형적인 dp 문제입니다. 그냥 대놓고 2차원 점화식을 선언해서 dp로 푸세요 라고 알려주고 있죠

$dp[x][y]= (1,1)\ 에서\ (x,y)\ 까지\ 만들때\ 나올\ 수\ 있는\ 소수의\ 최대\ 개수$

재귀함수를 이용해서 탑-다운 방식으로 풀어주었습니다.
소수는 에라토스체네스의 체로 걸러주었습니다.

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[1000][1000],sosu[1000010];

int f(int x,int y);
int get_sosu(int x,int y);

int main() {
    cin>>n;
    memset(dp,-1,sizeof(dp));
    for(int i=2;i*i<=1000000;i++){
        for(int j=i+i;j<=1000000;j+=i)
            sosu[j]=1;
    }
    dp[1][1]=0;
    cout<<f(n,n);
    return 0;
}
int f(int x,int y)
{
    if(x<1 || y<1)return 0;
    int &ret = dp[x][y];
    if(ret!=-1)return ret;

    ret=0;
    ret = max(ret,max(f(x-1,y),f(x,y-1)));
    ret+=get_sosu(x,y);
    return ret;
}
int get_sosu(int x,int y)
{
    int ty=y;
    int cnt=0;
    while(ty>0){
        ty/=10;
        x*=10;
    }
    x+=y;
    if(sosu[x])return 0;
    return 1;
}