[백준] 1463번: 1로 만들기 문제제목 풀이 및 해설(C++)

문제 이미지

풀이

일단 2보다는 3으로 나누는게 더 숫자를 작게 만들 수 있어보인다.

그렇다면 일단 3의 배수가 될때 까지 1을 뺀후 3으로 나누면 되는 것일까?

 

하지만 그렇게 하면 8같은 경우

3으로 나누는 것만 추구하면: 8->7->6->2->1 로 5회

2로만 나누면: 8->4->2->1로 4회

로 2로만 나눈 값이 더 작다.

 

즉, 고정된 공식이 명백히 더 빠르다는 것을 보장해 줄 수 없다.

 

명백한 공식이 없다면 결국 경우를 빠르게 계산 해야 한다. 그 경우를 모두 빠르게 제시하는 과정에서 동적 프로그래밍을 사용한다.

 

이 문제는 동적 프로그래밍 문제다. 차근차근 낮은 값들을 바탕으로 높은 값을 추론해내면 되는 것이다.

 

정수를 받아 그 길이 보다 1만큼 큰 배열을 만든다.

배열에 배열의 인덱스가 1에 도달하는 연산 횟수를 저장한다.

 

그리고 현재 배열의 (인덱스/3 번째의 값) OR (인덱스/2 번째의 값) OR (인덱스-1 번째의 값) 중 작은 값을 골라 거기에 1을 더해 저장하면 된다.

 

이전 수를 바탕으로 가장 적은 계산횟수를 계속 골라가는 것이다. 

 

해답 코드

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    fastio;
    int n;
    cin>>n;
    int arr[n+1] ={0};
    for(int i=2; i<n+1; i++){
        arr[i]=arr[i-1]+1;
        if (i%2==0){
            arr[i]=min(arr[i/2]+1,arr[i]);
        }
        if(i%3==0){
            arr[i]=min(arr[i/3]+1,arr[i]);
        }
    }
    cout<<arr[n];

    

}

 

PLUS

dp는 고정된 수학 공식을 사용할 수 없고, 하위값을 바탕으로 상위값을 추론할 수 있을 때 사용할 수 있다.

이때 배열의 인덱스가 곧 그 값이 되는 아이디어가 주로 사용된다.