이 글에서는 주어진 숫자 N의 합을 만들기 위해 필요한 한 자리 소수(2, 3, 5, 7)의 최소 개수를 구하는 방법을 다룹니다. 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 문제를 해결할 수 있습니다.
문제 설명
한 자리 소수인 2, 3, 5, 7을 여러 번 사용하여 그 합이 정확히 N이 되도록 할 때, 필요한 소수의 최소 개수를 구하는 것이 목표입니다. 만약 어떤 조합으로도 N을 만들 수 없다면 -1을 반환해야 합니다.
예시
N = 9인 경우를 살펴보겠습니다. 7 + 2 = 9이므로 두 개의 소수(7과 2)만 사용하면 됩니다. 따라서 정답은 2입니다.
반면 N = 1처럼 한 자리 소수들의 조합으로 절대 만들 수 없는 값이라면 -1을 반환하게 됩니다.
접근 방법: 동적 계획법
이 문제는 전형적인 동전 교환(Coin Change) 유형의 문제와 동일한 구조를 가집니다. 각 한 자리 소수(2, 3, 5, 7)를 '동전'으로 생각하고, N을 만드는 데 필요한 최소 '동전' 개수를 구하면 됩니다.
알고리즘 단계
- 크기가 N+1인 배열 arr을 선언하고, 모든 값을 매우 큰 값(무한대 역할)으로 초기화합니다.
- arr[0] = 1로 설정하고, 한 자리 소수인 2, 3, 5, 7에 해당하는 인덱스도 1로 초기화합니다.
- 1부터 N까지 반복하면서, 현재 위치 i에서 각 소수 p(2, 3, 5, 7)를 뺀 값(i - p)이 유효한 인덱스라면 arr[i]를 min(arr[i], 1 + arr[i - p])로 갱신합니다.
- 최종적으로 arr[n]이 여전히 초기값이라면 -1을 반환하고, 그렇지 않으면 arr[n]을 반환합니다.
구현 코드 (C++)
#include <iostream>
using namespace std;
// 인덱스 유효성 검사 함수
bool isValidIndex(int i, int val) {
return (i - val) < 0 ? false : true;
}
int getMinPrimes(int n) {
int arr[n + 1];
// 무한대 역할의 큰 값으로 초기화
for (int i = 1; i <= n; ++i) {
arr[i] = 1000000000L;
}
// 0과 한 자리 소수(2, 3, 5, 7)는 각각 1개로 표현 가능
arr[0] = arr[2] = arr[3] = arr[5] = arr[7] = 1;
for (int i = 1; i <= n; ++i) {
if (isValidIndex(i, 2)) {
arr[i] = min(arr[i], 1 + arr[i - 2]);
}
if (isValidIndex(i, 3)) {
arr[i] = min(arr[i], 1 + arr[i - 3]);
}
if (isValidIndex(i, 5)) {
arr[i] = min(arr[i], 1 + arr[i - 5]);
}
if (isValidIndex(i, 7)) {
arr[i] = min(arr[i], 1 + arr[i - 7]);
}
}
// 만들 수 없는 경우 -1 반환
return arr[n] == 1000000000L ? -1 : arr[n];
}
int main() {
int n = 9;
int result = getMinPrimes(n);
if (result != -1) {
cout << "필요한 최소 소수 개수: " << result << endl;
} else {
cout << "해당 합을 만드는 것이 불가능합니다" << endl;
}
return 0;
}
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.
필요한 최소 소수 개수: 2
복잡도 분석
- 시간 복잡도: O(N × 4) = O(N). N까지의 각 위치에서 네 개의 소수를 확인하므로 선형 시간에 해결됩니다.
- 공간 복잡도: O(N). 크기가 N+1인 DP 배열 하나만 사용합니다.
이처럼 동적 계획법을 활용하면 완전 탐색보다 훨씬 효율적으로 한 자리 소수의 최소 개수를 구할 수 있습니다.