[백준 1463] 1로 만들기 (DP)

• 안녕하세요 BlockDMask 입니다.

• 이번주(17년 12월 11~15일)

• 문제(1/3) 풀어보겠습니다.

0. 제목

• 백준 1463 1로 만들기 (DP)
• BOJ 1463 1로 만들기 (DP)

1. 문제 설명

• 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.
• 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 합니다.
  연산을 사용하는 횟수의 최소값을 출력하면 됩니다.

• --입력--
  첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 자연수 N이 주어집니다.

• --출력--
  첫째 줄에 연산을 하는 횟수의 최소 값을 출력합니다.

• ex) 입력이 10 이면, 
  9 (3번규칙)-> 3 (1번규칙) -> 1 (1번규칙)
  으로 3번을 출력하면 됩니다.

2. 풀이 과정

• Dynamic Programming(DP)를 이용하여 풀었습니다.
• top-down(recursive) 방식이 아닌 bottom-up(반복문) 방식을 이용하여 풀었습니다.

• Dynamic Programming 에서 가장 중요한 점화식을 규칙에서 뽑아
  배열로 확인 해보겠습니다.
  배열의 index가 숫자를 뜻하고 값이 그 index(숫자)까지 도달할때 최소 경우의 수 입니다.

• 1번 규칙 (3으로 나누어 떨어진다) : D[N] = D[N/3] + 1
  2번 규칙 (2로 나누어 떨어진다) : D[N] = D[N/2] + 1
  3번 규칙 ( 1 을 뺀다 ): D[N] = D[N-1] + 1

• 작은 문제서 부터 큰 문제를 풀어가는 방식입니다.
  숫자 1에서 부터
  2로 갈때의 경우의 수 중 가장 작은 방법.
  3으로 갈때의 경우의 수 중 가장 작은 방법.
  .
  .
  .
  N일때 가장 작은 방법.
  으로 구하면됩니다.

• (음..) 
• **queue를 이용한 BFS 방법을 통해서도 풀 수 있을거 같습니다.
• 다음 포스트에서는 BFS를 이용하여 풀어보겠습니다.

3. 소스 코드

//https://www.acmicpc.net/problem/1463
//BOJ_1463_one
//Dynamic Programming
 
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
 
class makeOne{
private:
    int n;  //n
    int arr[1000001];   //array
public:
    void setNum(){
        cin >> n;
        memset(arr, 0, sizeof(int) * (n+1));    //1부터 n까지 이므로 n+1.
    }
    
    //bottom up
    //1을 뺴는 계산부터 시작해서 작은 계산을 통해 미리 arr[i]에 (최대)값을 메모이제이션을 합니다.
    //2로 나누어 떨어지는지 3으로 나누어 떨어지는 경우에 앞에 계산한 arr[i/2]와 arr[i/3]과  현재의 arr[i]와 비교를 하여
    //그 중 최소 값을 arr[i]에 다시 저장(메모이제이션)합니다.
    
    void solution(){
        arr[1] = 0; //1일때는 횟수 0
        
        for(int i=2; i<=n; i++){
            arr[i] = arr[i-1] + 1;  //규칙 3번 : 1을 뺀다
            if(i%2 == 0){
                arr[i] = min(arr[i], arr[i/2]+1);   //규칙 2번 : 2로 떨어지는 경우
            }
            if(i%3 == 0){
                arr[i] = min(arr[i], arr[i/3]+1);   //규칙 1번 : 3로 떨어지는 경우
            }
        }
    }
    
    void printMin(){
        cout << arr[n];
    }
};
 
int main(void){
    makeOne one;
    one.setNum();
    one.solution();
    one.printMin();
    return 0;
}
 

4. 인증

문제 출처 - https://www.acmicpc.net/problem/1463

감사합니다.