백준 1463번 C++

https://assb.tistory.com/entry/%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0

백준 1463번: 1로 만들기

#include <iostream>

using namespace std;

int numbers[1000001];       //몇번 하는지 횟수 저장

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

int main(){
    numbers[0] = 0;  numbers[1] = 0;  numbers[2] = 1; numbers[3] = 1;

    int d_three, d_two, s_one;
    for(int i=4; i<1000001; i++){       //i는 i라는 숫자 1로 만들기 위한 for문이다. 1000001
        d_three=10000000; d_two=100000000; s_one=100000000;
        numbers[i] = i;

        if(numbers[i]%3 == 0){      //3으로 나누어 떨어지면
            d_three = numbers[i/3];
        }
        if(numbers[i]%2 == 0){
            d_two = numbers[i/2];
        }
        s_one = numbers[i-1];

        //i보다 작은 숫자는 최소값이 무조건 나와있는 상태일 것이다.
        int min = (d_three <= d_two && d_three <= s_one) ? d_three :       
            (d_two <= d_three && d_two <= s_one) ? d_two : s_one;  

        numbers[i] = min+1;
    }

    int a;
    cin >> a;
    cout << numbers[a] << "\n"; 
}

 

생각은 간단하게 하면 된다.

저도 처음에는 나누기함수, 빼기 함수 만들어서 하려고 했지만 결국 값들을 다 넣어두면 된다고 생각했다.

 

하지만 

for문을 위처럼 만들어서 실행을 하면

결국 4부터는 4보다 작은 값의 1로 만들기를 위한 최소값이 들어가 있을 것이고

5는 5보다 작은 값의 1로 만들기 위한 최소값이 들어가 있을 것이다.

결국 9999는 9999보다 작은 값(1~9998)의 1로 만들기 위한 최소값이 들어가 있을 것이고 9999는 1개의 단계를 더 했으니까 +1을 해주면 그것이 9999를 1로 만들기 위한 최소값이 되는 것이다.