2024/12/19 매일 백준

두 번째 날,
오늘은 다른 공부도 하느라 늦게 작성을 하게되었다. 작성 시점이 20일이 되더라도 ㅠㅠ 어쩔 수 없음

1463번: 1로 만들기

이런 문제이다.

입력이 주어지면 해당 수를 '1'까지 만드는데 최소 연산 개수를 출력하는 것이다.

1부터 연산을 구해보자

위와 같이 이전 단계의 값을 이용해서 계산 횟수를 구하면 된다.
단, 최소 횟수이므로 빼기 1과 나누기 값 중에서 가장 작은 값을 저장하면 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {

    int N = 0, A[1000001] = {0};

    cin >> N;

    A[1] = 1, A[2] = 1, A[3] = 1;

    for(int i=4;i<=1000000;i++) {
        
        A[i] = A[i-1] + 1;

        if(i % 3 == 0) {
            A[i] = min(A[i], A[i / 3] + 1);
        }
        if(i % 2 == 0) {
            A[i] = min(A[i], A[i / 2] + 1);
        }
    }

    cout << A[N] << endl;

    return 0;
}

맨 처음에는 이렇게 풀었는데, 생각해보니 N까지의 값만 구하면 되니, 1000000이 아닌 N으로 수정하였다.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {

    int N = 0, A[1000001];

    cin >> N;

    A[1] = 1, A[2] = 1, A[3] = 1;

    for(int i=4;i<=N;i++) {
        
        A[i] = A[i-1] + 1;

        if(i % 3 == 0) {
            A[i] = min(A[i], A[i / 3] + 1);
        }
        if(i % 2 == 0) {
            A[i] = min(A[i], A[i / 2] + 1);
        }
    }

    cout << A[N];

    return 0;
}

그래서 이렇게 제출하였는데, 어라라 또 안되는 것이다. 무엇이 문제일까 곰곰히 생각해보다 시간 제한이 0.15초에 걸리는 것 같아서

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {

    int N = 0, A[1000001];

    cin >> N;   

    for(int i=2;i<=N;i++) {
        
        A[i] = A[i-1] + 1;

        if(i % 3 == 0) {
            A[i] = min(A[i], A[i / 3] + 1);
        }
        if(i % 2 == 0) {
            A[i] = min(A[i], A[i / 2] + 1);
        }
    }

    cout << A[N];

    return 0;
}

로 제출하여서 통과했따 ~~ ^^

쉬운 거부터 하고있으니 익숙해지면은 난이도를 올려서 도전해봐야겠다