백준 1463번, 1로 만들가

백준 1463번 c++ 문제풀이

문제:

백준 1463

풀이:

1. dp로 접근했다.
2. 최소 횟수를 저장한 배열을 만든다. 이 배열을 dp[]라고 해보자.
3. 2부터 1로 만들 수 있는 횟수를 배열에 저장한다.
4. 입력값 input이 2로 나눌 수 있다면 dp[input]은 dp[input/2]와 dp[input-1]을 비교해 둘중 더 작은 횟수에 1을 더한값(2로 나누거나 1을 빼는 과정이 추가되었기에)이다.
5. 3으로 나눌 수 있는 수이면 위와 같은 과정을 수행해주면된다.
6. 2와 3 둘다 나뉜다면 위의 4, 5 과정에서 구한 값을 비교하여 둘중 더 작은 값을 저장 해주면 된다.
7. 2와 3 둘로 다 나뉘지 않는다면 무조건 dp[input] = dp[input-1]+1 이다.

코드:

#include <iostream>

using namespace std;

int dp[1000001];
void countp(int x){
    for(int i = 2 ; i <= x ;i++){
        if(i % 2 == 0 && i % 3 == 0){
            dp[i] = min(min(dp[i - 1], dp[i / 2]) + 1,min(dp[i - 1], dp[i / 3]) + 1);
        }
        else if (i % 2 == 0) {
            dp[i] = min(dp[i - 1], dp[i / 2]) + 1;
        } else if (i % 3 == 0) {
            dp[i] = min(dp[i - 1], dp[i / 3]) + 1;
        } else {
            dp[i] = dp[i - 1] + 1;
        }
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int x;

    cin >> x;

    
    countp(x);


    cout << dp[x];

    return 0;   
}   

처음 풀었을 때 2와 3 둘다 나눠지는 조건을 빼먹어 애를 먹었던 것 같다. 그 조건은 다른 분이 알려주셔서 빼먹은 것을 알 수 있었다.

감사합니다.