[코딩테스트/ 백준 알고리즘] BOJ.1463 : 1로 만들기(탑다운) (C++ 풀이)

문제

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

1463번: 1로 만들기

 

---

풀이

자료구조

- int input : 입력

- int dp[] : dp 테이블

 

알고리즘

- 다이나믹 프로그래밍

- 재귀 사용한  탑다운 방식

- 점화식 : dp[i] = min(DP(i / 2), DP(i / 3), DP(i - 1)) + 1

코드 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1000001] = {0};

int DP(int input) {

    //중복 계산 방지
    if(dp[input] != 0) {
        return dp[input];
    }

    else {
        if(input == 1){
            return 0;
        }
        // input이 2와 3으로 나눌 수 없으면 -1을 할 수밖에 없음
        else if(input % 2 != 0 && input % 3 != 0) {
            dp[input] = DP(input - 1) + 1;
            return dp[input];
        }
        // input이 3으로 나누어지지 않으면 2로 나누거나 -1을 한 값에서 작은 값을 선택
        else if(input % 3 != 0 ) {
            dp[input] = min(DP(input / 2), DP(input - 1)) + 1;
            return dp[input];
        }
        // input이 2로 나누어지지 않으면 3으로 나누거나 -1을 한 값에서 작은 값을 선택
        else if(input % 2 != 0) {
            dp[input] = min(DP(input / 3), DP(input - 1)) + 1;
            return dp[input];
        }
        // input이 2와 3으로 나누어지면 둘 중 작은 값 선택
       else {
            dp[input] = min(DP(input / 3), DP(input / 2)) + 1;
            return dp[input];
        }
    }
}

int main() {

    int input = 0;

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> input;
    DP(input);
    cout << dp[input];

    return 0;
}

 

---

총평

DP 뽀개기 프로젝트에 의해 '2839 : 설탕 배달' 다음으로 풀어본 문제다.

DP에 대한 이해가 어느정도 된 상태라 쉽게 풀었던 거 같다.

근데 설탕 배달에 뇌가 지배당한 탓에 코드가 너무 비슷하다.

이 문제도 탑다운과 바텀업 방식 두 가지로 풀어보았다. 지금 이 글에서는 탑다운 방식을 통해 풀었다.

다음 글에는 바텀업 방식을 사용해서 푼 코드를 올리겠다.