BOJ 19576 - 약수 링크
(2024.03.12 기준 G3)

문제

$N$개의 정수 $a_1$, $\dots$, $a_N$이 주어진다. 서로 다른 임의의 두 $a_i$, $a_j$에 대해 항상 $a_i$가 $a_j$로 나누어 떨어지거나 $a_j$가 $a_i$로 나누어 떨어져야 한다.
조건을 만족하도록, 임의의 $a_i$를 골라 원하는 양의 정수로 바꿀 수 있는, "와우매직"을 사용해야 하는 횟수의 최솟값 출력

알고리즘

눈에 잘 보이지 않는 DP 문제

풀이

일단 "와우매직"으로 임의의 원소를 $1$로 바꿔야 함을 먼저 알아야 한다. 어떤 양의 정수든 $1$로 나누어 떨어지기 때문이다.

만약 $a$가 정렬되어 있다면? $i<j$인 모든 $a_i$와 $a_j$에 대해 $a_j$가 $a_i$로 나누어 떨어지는지 확인하면 된다. 즉, $[i,j]$ 구간에서의 최솟값은 다른 구간과 독립적이 된다. 그럼 이제 점화식을 세워보자.

$f(l, r)$은 $[l,r]$ 구간의 모든 수에 "와우매직"을 사용, 즉 $r - l + 1$이 된다.

$dp[i]$를 $[i,N-1]$ 구간에 대한 최솟값으로 정의하자. (0-based index)
그러면 $dp[i]$의 초기값은 $a_i$를 제외한 모든 수에 "와우매직"을 사용하는 횟수이므로 $f(i+1,N-1)$이 된다. 그리고 $j > i; a_j \bmod a_i = 0$을 만족하는 모든 $j$에 대해 $f(i+1, j-1) + dp[j]$를 구해 최솟값으로 갱신하면 된다.
$a_i$와 $a_j$가 만족하는 관계이면, $[i+1,j-1]$ 구간의 모든 수에 "와우매직"을 사용하고 $a_j$가 가지고 있는 최솟값($[j,N-1]$ 구간)을 가져가는 느낌이라고 이해하면 된다.

이제 $i$에 대한 결과 $res[i]$는 $f(0, i-1) + dp[i]$가 된다. $[0,i-1]$ 구간의 모든 수에 "와우매직"을 사용한 값과 $[i,N-1]$ 구간의 최솟값을 더한 것이다. 이렇게 나온 모든 $i$에 대한 $res[i]$의 최솟값이 정답이 된다.

코드

• C++

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int a[N]; for (int i = 0; i < N; i++) cin >> a[i];

    // f(l, r) : [l, r] 구간의 모든 수를 1로 바꾸기 = r - l + 1
    // dp[i] : [i, N-1] 구간에서의 "와우매직" 사용 횟수의 최솟값
    // dp[i] = f(i+1, j-1) + dp[j] (j > i; a[j] % a[i] == 0)
    // a를 정렬한 뒤, N-1부터 0까지 dp를 채워간다.
    // res[i] = f(0, i-1) + dp[i]

    sort(a, a + N);
    int dp[N], ans = N; dp[N - 1] = 0;
    for (int i = N - 1; i >= 0; i--){
        dp[i] = N - 1 - i; // f(i+1, N-1)
        for (int j = i + 1; j < N; j++)
            if (!(a[j] % a[i])) dp[i] = min(dp[i], j - i - 1 + dp[j]); // f(i+1, j-1) + dp[j]
        ans = min(ans, i + dp[i]); // f(0, i-1) + dp[i]
    }

    cout << ans;
}

• Python (PyPy3)

import sys; input = sys.stdin.readline

N = int(input())
a = sorted(map(int, input().split()))

# f(l, r) : [l, r] 구간의 모든 수를 1로 바꾸기 = r - l + 1
# dp[i] : [i, N-1] 구간에서의 "와우매직" 사용 횟수의 최솟값
# dp[i] = f(i+1, j-1) + dp[j] (j > i; a[j] % a[i] == 0)
# a를 정렬한 뒤, N-1부터 0까지 dp를 채워간다.
# res[i] = f(0, i-1) + dp[i]

dp = [0] * N; ans = N
for i in range(N - 1, -1, -1):
    dp[i] = N - 1 - i # f(i+1, N-1)
    for j in range(i + 1, N):
        if not a[j] % a[i]:
            dp[i] = min(dp[i], j - 1 - i + dp[j]) # f(i+1, j-1) + dp[j]
    ans = min(ans, i + dp[i]) # f(0, i-1) + dp[i]

print(ans)