[BOJ] 백준 1463번 1로 만들기 풀이

| |
백준 온라인 저지 백준 1463번 - 1로 만들기 C++ 풀이


문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.


입력

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.


출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.


풀이

얼핏보면 조금만 생각하면 탐욕법으로 풀이할 수 있는 문제처럼 보인다. 가장 많이 하게되는 실수는 다음과 같다.

큰 수로 나눌수록 숫자가 작아지므로 3으로 나눠보고, 안되면 2로 나눠보고, 또 안되면 1을 빼자!

하지만 이렇게 풀 경우 문제의 예제 입력부터 통과하지 못하게 된다. 예를 들어 10과 같은 경우, 처음에 1을 먼저 빼고 진행하는 경우가 최소이다. 이 뿐만 아니라 수많은 예외사항이 존재하므로 이 문제는 그리디로 풀리지 않고, 완전탐색을 통해 모든 경우의 수를 확인하여야 한다. 그런데 재귀를 통해 완전탐색을 구현하고 나면 같은 수에 대한 연산이 여러번 수행되는 중복이 발생함을 알 수 있다. 따라서 메모이제이션 기법을 적용해 다이나믹 프로그래밍으로 풀어주면 된다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int cache[1000001];

int solve(int n){
    if(n==1) return 0; // 1이 되면 종료

    int& ret=cache[n];
    if(ret!=0) return ret; // 메모이제이션

    ret=solve(n-1)+1; // 1을 빼는 경우의 수
    if(n%3==0) ret=min(ret,solve(n/3)+1); // 3으로 나누는 경우의 수
    if(n%2==0) ret=min(ret,solve(n/2)+1); // 2로 나누는 경우의 수
    
    return ret;
}

int main(){
    int N; cin>>N;
    cout<<solve(N);
    return 0;
}
0%