[Python] 2421번 저금통

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

2421번: 저금통

---

 

23/03/12

 

 

전형적인 2차원 DP문제로, 현재 상태를 잘 정의하고 점화식을 세우면 쉽게 해결할 수 있다.

---

 

문제 접근 방식:

 

 

문제를 보고 처음에 발견한 사실은, 첫번째 저금통에 돈을 넣거나 두번째 저금통에 돈을 넣거나 둘 중 하나의 상태로만 갈 수 있다는 사실을 알아냈다.

 

이를 통해 $\mathrm{DP}[i][j]$ $=$ 첫번째 저금통에 $i$원을 넣고, 두번째 저금통에 $j$원을 넣었을 때, 소수가 가장 많이 나온 횟수로 정의 하였다.

 

이렇게 상태를 정의하고 나니, 위에서 발견한 사실을 토대로 점화식을 세울 수 있었다.

 

$$\mathrm{DP}[i][j] = \mathrm{max}(\mathrm{DP}[i-1][j], \mathrm{DP}[i][j-1]) + \mathrm{is\_prime}(i, j)$$

 

이때, $\mathrm{is\_prime}(i, j)$는 $i$와 $j$를 이어붙인 수가 소수라면 $1$을, 소수가 아니라면 $0$을 반환해주는 함수이다.

 

이렇게 점화식을 세울 수 있었던 이유는, 첫번째 저금통에 $1$원을 넣거나, 두번째 저금통에 $1$원을 넣거나, 둘 중 하나의 행동만 가능하기 때문이다.

 

 

$i$와 $j$를 이어붙인 수는 최대 $999,999$까지 가능하므로, 백만짜리의 배열을 선언해 에라토스테네스의 체를 만들어주었다.

 

이후, 빠르게 소수를 판단하기 위해, 체에 넣었던 숫자들을 모두 $\mathrm{primes}$라는 set에 넣어줌으로써, $O(1)$의 시간복잡도로 소수를 판단할 수 있도록 했다.

 

이때 중요한 것은, $11$은 소수로 포함시키지 않았는데, 그 이유는 가장 처음의 경우(1, 1)는 소수로 세지 않는다고 했기 때문이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2421번 저금통
# DP, 소수 판정, 에라토스테네스의 체
'''
접근 방법:
DP[i][j] = 첫번째 저금통에 i원을 넣고, 두번째 저금통에 j원을 넣었을 때,
소수가 가장 많이 나온 횟수
DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + is_prime(i, j)
'''
sieve = [1 for _ in range(1000000)]
sieve[0], sieve[1] = 0, 0
for i in range(2, 1001):
    if sieve[i]:
        for j in range(2*i, 1000000, i):
            sieve[j] = 0
primes = set()
for i in range(12, 1000000):
    if sieve[i]:
        primes.add(i)

def is_prime(a, b):
    num = int(str(a)+str(b))
    if num in primes:
        return 1
    return 0

N = int(input())
DP = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + is_prime(i, j)
print(DP[N][N])