BOJ 1463번 1로 만들기

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1463/1463/%EC%86%8C%EC%8A%A4.cpp

 

주어진 숫자를 가지고 1을 찾아가는 단순한 방법을 사용하면

테스트케이스의 수가 많아 시간초과에 걸리게 된다.

1로 가게 되는 경우를 거꾸로 생각해서 최적의 계산 횟수를 저장해둔다면 1~1000000 의

모든 경우를 1번만 계산한 후 테스트케이스에 맞게 바로바로 출력해주면 된다.

 

#include <iostream>
using namespace std;
#pragma warning(disable:4996)
 
int arr[1000001];
 
int main() {
    arr[1] = 0, arr[2] = 1, arr[3] = 1, arr[4] = 2;
    int number;
    cin >> number;
 
    for (int i = 5; i <= number; i++) {
        if (i % 2 != 0 && i % 3 != 0) {
            arr[i] = arr[i - 1] + 1;
        }
        else {
            arr[i] = arr[i - 1] + 1;
            if (i % 2 == 0) if (arr[i] > arr[i / 2] + 1) arr[i] = arr[i / 2] + 1;
            if (i % 3 == 0) if (arr[i] > arr[i / 3] + 1) arr[i] = arr[i / 3] + 1;
        }
    }
    printf("%d", arr[number]);
}

 

복습) 20.02.08