백준 1463 - 1로 만들기

<실패했던 접근 방법 - 1>

1. 예제에서 10의 경우 2로 나누어떨어지지만, 10을 2로 나눠서 진행하는 것보다 10에서 1을 빼서 3으로 나누는 방법이 연산 횟수가 더 적다.

2. 2로 나누어떨어지더라도 1을 뺐을 때 3으로 나누어 떨어지면 그렇게 진행하는 것이 더 횟수가 적다고 판단

3. 메인 함수에서 조건문을 통해 다음과 같은 방식으로 알고리즘을 구현

<실패했던 알고리즘 - 1>

1. 조건문을 통해 2를 반복

2-1. 숫자가 3으로 나누어 떨어지면, 3으로 나누고 연산 횟수를 1 만큼 증가하고 2-5로 넘어간다. 그렇지 않으면 2-2로 넘어간다.

2-2. 숫자를 1 만큼 뺐을 때 3으로 나누어 떨어지면, 1을 빼고 3으로 나눈 후 연산 횟수를 2 만큼 증가하고 2-5로 넘어간다. 그렇지 않으면 2-3으로 넘어간다.

2-3. 숫자가 2로 나누어 떨어지면, 2로 나누고 연산 횟수를 1 만큼 증가하고 2-5로 넘어간다. 그렇지 않으면 2-2로 넘어간다.

2-4. 숫자를 1 만큼 빼고 연산 횟수를 1 만큼 증가한다. 2-5로 넘어간다.

2-5. 현재 숫자가 1이면 종료하고, 아니면 2-1부터 다시 반복 진행

<실패 이유>

 주어지는 입력 값이 작을 경우는 잘 동작하지만 숫자가 커지면 되지 않는 경우가 발생

 숫자가 커질 경우 위의 조건대로 하는 것보다 더 작은 경우가 있다는 것이기 때문에 어떠한 경우인지를 고민해봄

<실패했던 접근 방법 - 2>

1. 주어진 숫자로 1까지 만들어보는 연산을 다양하게 시도해본다.

2. 시도했던 방법들 중 연산 횟수가 가장 적은 것을 정답으로 출력한다.

<실패 이유>

 사실 실패했다기보다는 구현을 하다가 중단했다. 입력 숫자가 1000000까지도 주어질 수 있는데 이 방법으로 프로그램을 짜면 좋지 않은 코드가 될 것 같았다.

<접근 방법>

1. 특정 수가 주어졌을 때, 연산을 1회 거친 다음의 최소 횟수는 해당 수가 주어졌을 때의 최소 연산 횟수를 구하는 것과 같다.

2. 1~10까지를 위의 방법으로 최소 횟수를 정리해보면 다음과 같다.

 [1] - 0번

 1. 1

 [2] - 1번

 1. 2 -> 1 (연산 2)

 2. 2 -> 1 (연산 3)

 [3] - 1번

 1. 3 -> 1 (연산 1)

 [4] - 2번

 1. 4 -> 2 -> 1 (연산 2, 연산 2) 

 2. 4 -> 2 -> 1 (연산 2, 연산 3)  

 3. 4 -> 3 -> 1 (연산 3, 연산 1)

 [5] - 3번

 1. 5 -> [4] (연산 3, 2번)

 [6] - 2번

 1. 6 -> [3] (연산2, 1번) 

 2. 6 -> [2] (연산1, 1번)

 [7] - 3번

 1. 7 -> [6] (연산3, 2번)

 [8] - 3번

 1. 8 -> [4] (연산2, 2번)

 [9] - 2번

 1. 9 -> [3] (연산1, 1번)

 [10] - 3번

 1. 10 -> [9] (연산3, 2번)

3. 입력 숫자가 1~3인 경우는 미리 입력해준다.

4. 입력 숫자가 4 이상인 경우 4부터 주어진 입력 숫자까지 최소 연산 횟수를 구해나간다.

5. 특정 수의 최소 횟수를 구하기 위해서는 연산 1~3이 가능한지를 체크해보고 가능한 연산을 진행한 후, 가장 최소값을 최소 연산 횟수로 판단한다.

<위의 방법으로 성공한 코드는 다음과 같다>

#include <iostream>
 
using namespace std;
 
int checkMinPath(int *cnt, int N) {
    int min = 1000000;
    int temp;
 
    if(N%3 == 0) {
        temp = cnt[N/3] + 1;
        min = temp;
    }
    if(N%2 == 0) {
        temp = cnt[N/2] + 1;
        if(temp < min)
            min = temp;
    }
 
    temp = cnt[N-1] + 1;
    if(temp < min)
        min = temp;
 
    return min;
}
 
int main(void) {
    int N, min, tempCnt;
    cin >> N;
    int cnt[N+1];
    cnt[1] = 0;
    cnt[2] = 1;
    cnt[3] = 1;
 
    for(int i=4; i<=N; i++) {
        cnt[i] = checkMinPath(cnt, i);
    }
 
    cout << cnt[N] << "\n";
}