[백준] 1463 | 1로 만들기 | C++

풀이의 핵심은 다이나믹 프로그래밍이다.

0. dp[i]의 값은 'i를 1로 만들기 위한 최소 연산 횟수'를 의미한다.

1. 2부터 n까지 i반복:
    dp[i]는 dp[i-1]에 1을 더한 값으로 초기화.
    만약 i가 2의 배수라면: dp[i]=min(dp[i], dp[i/2]+1)로 초기화한다.
    만약 i가 3의 배수라면: dp[i]=min(dp[i], dp[i/3]+1)로 초기화한다.
    
2. dp[n]을 출력한다.

 

0.

dp를 벡터로 선언하면, OutofBounds에 안걸린다.

 

1.

i가 6의 배수라면 2로도, 3으로도 나눠 떨어진다.

3으로 나누었을 때의 횟수가 더 적으므로

2부터 처리하도록 한다.

 

정답 소스코드

#include<bits/stdc++.h>
using namespace std;

int n;

int main() {
    ios_base::sync_with_stdio(0);
    cin>>n;
    vector<int> dp(n+1, 0);
    for(int i=2; i<=n; i++) {
        dp[i]=dp[i-1]+1;
        if(i%2==0) dp[i]=min(dp[i], dp[i/2]+1);
        if(i%3==0) dp[i]=min(dp[i], dp[i/3]+1);
    }
    cout<<dp[n]<<"\n";
    return 0;
}