<알고리즘 문제풀이&연습>/[C++] 백준, 프로그래머스 등등

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

BlockDMask 2017. 12. 12. 20:39
반응형
  • 안녕하세요 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. 소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//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, 0sizeof(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;
}
 
cs


4. 인증


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

감사합니다.


반응형