[백준] 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은 세지 않는다.

 

풀이

전형적인 DP 문제이다.

2차원 배열을 만들고 i,j를 이어붙인 수가 소수면 +1을 하고 아니면 +0을 하는 방식으로 접근했다. 

첫번째 저금통에 돈을 넣거나, 두번째 저금통에 돈을 넣기 때문에 반드시 둘 중 하나를 선택해야 하는 방식이기 때문에 다음의 점화식을 도출 할 수 있다.

 

DP[i][j] = MAX( DP[i-1][j] , DP[i][j-1] ) + ( i,j를 이어붙인 수가 소수면 1, 아니면 0 )

 

소수 판별을 위해 999999크기의 배열로 에라스토테네스의 체를 구현 하고 계산을 하면 O(1)으로 풀 수 있다. 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .split("\n");
const N = Number(input[0]);
let dp = Array(N + 1)
  .fill()
  .map(() => new Array(N + 1).fill(0));
let arr = Array(999999 + 1)
  .fill(true)
  .fill(false, 0, 2);

for (let i = 2; i * i <= 999999; i++) {
  if (arr[i]) {
    for (let j = i * i; j <= 999999; j += i) {
      arr[j] = false;
    }
  }
}
arr[11] = false;

for (let i = 1; i <= N; i++) {
  for (let j = 1; j <= N; j++) {
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    let p = Number(i + "" + j);

    dp[i][j] += arr[p] ? 1 : 0;
  }
}
console.log(dp[N][N]);