1463 - 1로 만들기

• 난이도: 실버 3
• 날짜: 2023년 2월 26일
• 상태: Correct
• 추가 검토 여부: No
• 알고리즘 : DP

solution

• 다이나믹 프로그래밍을 이용한다. 이전 단계의 정답을 다음 단계의 정답에 사용할 수 있는 문제이다.
• 1, 2, 3에 대해서만 미리 값을 정해준다. 그 이후의 값들에 대한 연산 결과는 해당 수를 3으로 나누거나, 2로 나누거나 1로 뺀 수의 연산값 중 가장 작은 값에 1을 더한 값이다.
• 물론 3으로 나누어떨어지거나 2로 나누어 떨어질 경우에만 해당 경우에 대해 고려하고 그렇지 않다면 1로 뺀 수의 연산값에 1을 더한 값이 연산값이 된다.

code

#include <iostream>
#include <climits>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int * arr = new int[1000001];
    for(int i = 0; i < 1000001; i++)
        arr[i] = 0;
    arr[2] = 1; arr[3] = 1;

    for(int i = 4; i < 1000001; i++)
    {
        int min = INT_MAX;
        if(i%2==0 && i%3==0)
        {
            min = (arr[i/2] < arr[i/3]) ? arr[i/2] : arr[i/3];
            min = (min < arr[i-1]) ? min : arr[i-1];
        }
        else if(i%2==0 && i%3!=0) min = (arr[i/2] < arr[i-1]) ? arr[i/2] : arr[i-1];
        else if(i%2!=0 && i%3==0) min = (arr[i/3] < arr[i-1]) ? arr[i/3] : arr[i-1];
        else min = arr[i-1];
        
        arr[i] = min + 1;
    }

    cout << arr[N] << endl;

    return 0;
}

ref

1463번: 1로 만들기