[C++] 백준 1463번 : 1로 만들기 (S3)

#문제

www.acmicpc.net/problem/1463

1463번: 1로 만들기

#풀이 & 학습한 내용

우선 최솟값을 구할 때 #include <algorithm>의 min에 {}로 대소 비교할 값들을 묶어서 전달하여 최솟값을 구했다. 또한, dp를 이용할 때 먼저 basis case로 숫자가 2와 3일 때의 dp배열에 1 값을 넣었으며, 이후에는 for문을 통해 N까지 순차적으로 계산하였다. 이때, 경우는 2와 3으로 모두 나누어 떨어질 때, 2로만 나누어 떨어질 때, 3으로만 나누어 떨어질 때, 2와 3 모두로 나누어 떨어지지 않을 때로 나누었다. 연산의 횟수이므로 이전의 optimization에 1을 더해주어 dp배열에 값을 넣었다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int dp[1000002];
 
int main(void) {
    int N;
    cin >> N;
    dp[2] = 1; dp[3] = 1;
    for (int i = 4; i <= N; i++) {
        if (i % 6 == 0) {
            dp[i] = min({ dp[i / 3],dp[i / 2], dp[i - 1] }) + 1;
        }
        else if (i % 2 == 0 && i % 3 != 0) {
            dp[i] = min({ dp[i / 2], dp[i - 1] }) + 1;
        }
        else if (i % 2 != 0 && i % 3 == 0) {
            dp[i] = min({ dp[i / 3], dp[i - 1] }) + 1;
        }
        else {
            dp[i] = dp[i - 1] + 1;
        }
    }
    cout << dp[N] << "\n";
}

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_1463.cpp

HoYoungChun/BOJ_algorithm