문제 설명
다섯 개의 정수 N, A, B, C, D가 주어집니다. 숫자 0에서 시작해 N에 도달해야 하며, 아래 연산을 수행할 때마다 정해진 코인을 지불해야 합니다.
- 현재 숫자에 2를 곱한다 — A코인 지불
- 현재 숫자에 3을 곱한다 — B코인 지불
- 현재 숫자에 5를 곱한다 — C코인 지불
- 현재 숫자를 1 증가 또는 감소시킨다 — D코인 지불
연산은 원하는 만큼, 어떤 순서로든 반복 수행할 수 있습니다. 목표는 N에 도달하는 데 필요한 최소 코인 수를 구하는 것입니다.
입력 예시와 풀이 과정
입력이 N = 11, A = 1, B = 2, C = 2, D = 8일 때 출력은 19입니다. 초기 값 x는 0이며, 최적의 연산 순서는 다음과 같습니다.
- 8코인으로 x를 1 증가 → x = 1
- 1코인으로 x에 2를 곱함 → x = 2
- 2코인으로 x에 5를 곱함 → x = 10
- 8코인으로 x를 1 증가 → x = 11
총 비용은 8 + 1 + 2 + 8 = 19코인입니다.
풀이 접근 방법
이 문제는 메모이제이션(memoization)을 적용한 재귀 함수로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 목표 값 n에서 거꾸로 거슬러 올라가며, 2·3·5로 나누어 떨어지는 지점까지 ±1 연산으로 보정하는 것입니다.
- n을 2로 나눌 때 나머지만큼 ±1 연산이 필요하고, 각 연산마다 D코인이 소요됩니다.
- 나머지가 남는 경우에는 내림(n / 2)과 올림(n / 2 + 1) 방향을 모두 고려해 더 저렴한 쪽을 선택합니다.
- 곱셈을 활용하는 것보다 처음부터 1씩 n번 증가시키는 비용(n × D)이 더 저렴하다면 그 값을 채택합니다.
알고리즘 단계
정수형 키와 값을 가지는 맵 f를 정의한다 (계산 결과 캐싱용)
정수형 키와 불린형 값을 가지는 맵 vis를 정의한다 (방문 여부 기록용)
calc(n) 함수를 정의한다:
n이 0이면 0을 반환한다
n을 이미 방문했다면 f[n]을 반환한다
vis[n] := 참
res := calc(n / 2) + (n mod 2) * d + a
n mod 2가 0이 아니면:
res := min(res, calc(n / 2 + 1) + (2 - n mod 2) * d + a)
res := min(res, calc(n / 3) + (n mod 3) * d + b)
n mod 3이 0이 아니면:
res := min(res, calc(n / 3 + 1) + (3 - n mod 3) * d + b)
res := min(res, calc(n / 5) + (n mod 5) * d + c)
n mod 5가 0이 아니면:
res := min(res, calc(n / 5 + 1) + (5 - n mod 5) * d + c)
(res - 1) / n + 1 > d이면:
res := n * d
f[n]에 res를 저장한 뒤 반환한다
main 함수에서 a, b, c, d를 설정하고 calc(n)을 호출한다
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d;
map<long, long> f;
map<long, bool> vis;
long calc(long n){
if (!n)
return 0;
if (vis.find(n) != vis.end())
return f[n];
vis[n] = 1;
long res = calc(n / 2) + n % 2 * d + a;
if (n % 2)
res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a);
res = min(res, calc(n / 3) + n % 3 * d + b);
if (n % 3)
res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b);
res = min(res, calc(n / 5) + n % 5 * d + c);
if (n % 5)
res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c);
if ((res - 1) / n + 1 > d)
res = n * d;
return f[n] = res;
}
int solve(int N, int A, int B, int C, int D){
a = A;
b = B;
c = C;
d = D;
return calc(N);
}
int main(){
int N = 11;
int A = 1;
int B = 2;
int C = 2;
int D = 8;
cout << solve(N, A, B, C, D) << endl;
}
입력
11, 1, 2, 2, 8
출력
19
코드 동작 원리
calc() 함수는 재귀적으로 호출되며, 한 번 계산한 값은 f 맵에 캐싱되어 중복 계산을 방지합니다. n을 2, 3, 5로 나누는 세 가지 경우를 각각 살펴보고, 나머지만큼의 ±1 비용(D)과 해당 배수 연산 비용(A, B, C)을 더한 값을 후보로 삼습니다. 나머지가 있을 때는 내림 방향과 올림 방향 중 더 저렴한 쪽을 선택합니다. 마지막으로 (res - 1) / n + 1 > d 조건을 통해 곱셈 없이 처음부터 1씩만 증가시키는 방법(n × D)이 더 유리한지 검사하여 최종 최솟값을 결정합니다. 이처럼 탐색 공간이 로그 스케일로 줄어들기 때문에 큰 N에 대해서도 빠르게 답을 구할 수 있습니다.