1463)1로 만들기

https://www.acmicpc.net/problem/1463

몇 번의 뻘 짓으로 이 문제를 풀 수 있었다.

10을 1로 만들기 위해 연산하는 방법은 여럿 있을 수 있다.

처음에 생각했던 방법인데 최소 횟수가 아니었다.

10->5->4->2->1

예제 입력에서 어떻게 3번의 연산으로 10을 1로 만들 수 있었을까?

친절하게도 힌트에 잘 나와있다. 

10->9->3->1

이렇게 연산을 수행하면 최소의 횟수로 1을 만들 수 있다.

여기서 눈여겨 볼만한 점은 9를 최소의 연산으로 1을 만드는 방법도 

10을 1로 만드는 방법과 크게 다르지 않다는 것이다.

3을 1로 만드는 방법도 위와 크게 다르지 않다.

그렇다면 역으로 생각해서 1부터 시작해 n까지 

바닥부터 최소 연산 횟수를 구해가면 되지 않을까?

n 미만의 각 수를 1로 만들기 위해 최소 연산 횟수를 저장하는 배열의 초기 상태는 위와 같다.

여기서 2의 최소 연산 횟수를 어떻게 구할 수 있을까?

우선 인덱스 2를 가지고서 '연산 -1'를 수행해 그렇게 얻은 인덱스로 배열에 접근하고 그 값을 min에 저장한다.

이후에 같은 인덱스에 대해 '연산 /3'과 연산 /2'가 가능하다면 수행하고 그렇게 얻은 값으로 배열에 접근한다.

그 값과 min값을 비교해 작다면 min에 넣는다.

위 과정이 끝나고 얻은 min은 '연산 -1' 또는 '연산 /3' 또는 '연산 /2'를 한 번 수행한 값을 반영하지는 않아

min+1이 인덱스 i를 1로 만드는 최소 연산 횟수가 될 것이다.

그러니 2를 1로 만들기 위한 최소 연산 횟수는 1이다.

#include<stdio.h>
#define MAX 100001
 
int min(int A, int B) {
    return (A < B) ? A : B;
}
 
int main() {
    int A[MAX];
    int minOperNum;
    int n;
 
    scanf("%d", &n);
 
    A[0] = 0;
    A[1] = 0;
 
    for (int i = 2; i <= n; i++) {
        minOperNum = A[i - 1];
        if (i % 3 == 0) {
            minOperNum = min(A[i / 3], minOperNum);
        }
        if (i % 2 == 0) {
            minOperNum = min(A[i / 2], minOperNum);
        }
        A[i] = minOperNum + 1;
    }
 
    printf("%d\n", A[n]);
 
    return 0;
}