[백준 1463] 알고리즘 43일차 : 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

동적계획법 C++

문제는 위에 사진 참고 (설명 매우 귀찮다 딱히 요약할 것도 없응께)

N의 범위는 1부터 10^6 까지

 

접근방법

n개의 정수 배열을 사용한다. 배열에는 해당 수가 1이 되는데에 필요한 연산의 최소 횟수가 저장된다.

1: 0회, 2: 1회, 3: 1회까지 미리 저장해두고

4부터는 [ 1을 뺀 수의 연산 최소횟수 + 1 , 3으로 나눈 값의 연산 최소횟수 + 1 (3으로 나누어질때만), 2로 나눈 값의 연산 최소횟수 + 1 (2로 나누어질때만) ] 이 중 가장 작은 값을 해당 인덱스의 배열에 저장한다. 

(설명 진짜 못해먹겠음)

 

이제 DP에 적응한 것 같다. 빨리 푼다.

처음에 한 번 틀렸는데 1에 1저장해서.. 1이 1이되려면 연산횟수는 0..나처럼 멍청한짓 하는 사람 없겠지

 

소스코드

#include <iostream>
using namespace std;

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