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

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

1463번: 1로 만들기

문제분석

1. 분류
   • DP(동적계획법)
2. 문제설명
   • 입력받은 수를 최소한의 연산으로 1로 만들기
   • 연산은 3종류
     1. x-1
     2. if(x % 3 == 0), x / 3
     3. if(x % 5 == 0), x / 5 
   • 동적계획법 Bottom-up 방식으로 진행

 

입력

10

출력

3

코드

#include<iostream>
#include<vector>
#include <cstring>
using namespace std;

vector<int>dp;
int main() {
    int n;
    cin >> n;
    dp.assign(n+1,-1);
    dp[1] = 0;
    for (int x = 2; x <= n; x++) {
        int tmp = dp[x - 1] + 1;
        if (x % 2 == 0) tmp = min(tmp, dp[x / 2] + 1);
        if (x % 3 == 0) tmp = min(tmp, dp[x / 3] + 1);
        dp[x] = tmp;
    }

    cout << dp[n];
    return 0;
}

 

문제풀이

1. Bottom up 방식으로 입력받은 정수의 값을 도출한다.
   
   • 작은 값 dp[0],dp[1],dp[3]을 구해서 -> 큰 값(목표 값) dp[n]의 값을 구할 수 있다.
2. 연산의 최소 횟수를 구하고 싶은 정수 N을 입력받는다.
3. vector 형태의 dp 배열을 생성한다.
   
   • 배열의 크기는 N으로 설정한다.  N번 까지 연산 횟수를 구해야 하기 때문이다.
   • 배열의 모든 값을 -1로 초기화한다. 연산의 횟수를 dp탐색을 통해 업데이트 한다.
   • dp[1]은 더 이상 연산할 필요가 없는 수<목표값>이므로 1이다.
4. dp[1]까지의 값을 구했으니, dp[2]부터 dp[N]까지 구하는 반복문을 수행한다.
5. 반복문에서는 3개의 연산 중 가능한 모든 연산의 값을 구한다. 그 중 최소값이 dp[x]의 값이다.
6. 손으로 디버깅한 결과는 아래와 같다