[백준/Baekjoon] 1463 1로 만들기 C++ :: Dynamic Programming

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

1463번: 1로 만들기

1. Dynamic programming(동적 계획법)

- 하나의 큰 문제를 작은 문제로 나누어 푸는 방법

- 재귀로 풀게되면 계산했던 경우의 수도 한번 더 하기 때문에 메모이제이션(Memoization)을 통해 계산한 값을 배열에 저장하고 다음 호출때 이전에 계산했던 값을 만나게 되면 계산하지 않고 값을 불러와서 사용함.

- 시간복잡도를 현저히 줄일 수 있음.

 

---

2. Logic

1. 조건에 맞춰 3가지 분기를 만든다.

2. 완성된 수가 주어지기 때문에 주어진 수에서 1로 만들어가며 실행한다

3. 기저조건은 수가 1이 되면 리턴한다.

 

 

 

#include<bits/stdc++.h>

using namespace std;

const int INF = 987654321;

vector<int> dp(1000001, -1);

//반환값 : 연산을 사용한 최소 횟수
//cur : 계속해서 갱신되는 현재값
int solve(int cur) {
    if(cur == 1) return 0;	//기저조건
    int &ret = dp[cur];		//dp테이블을 참조
    if(ret != -1) return ret;	//이전에 동일한 연산을 했을 경우 추가 계산이 아닌 이전에 계산했던 값 불러오기
    ret = INF;	//문제에서 연산 사용 횟수 최솟값이라고 했기 때문에 말도 안되게 큰값 넣어서 최솟값 갱신
    if(cur % 3 == 0) {
    	//조건에 부합하면 재귀로 나눈값을 넣어주고 연산을 한 횟수기때문에 + 1
        ret = min(ret, solve(cur / 3) + 1);	
    }
    if(cur % 2 == 0) {
        ret = min(ret, solve(cur / 2) + 1);
    }
    ret = min(ret, solve(cur - 1) + 1);

    return ret;
}

int main() {
    int n;
    cin >> n;

    cout << solve(n);    
}

 

코드에서 잘 이해가 안가는 부분은 댓글로 남겨주시면 최대한 찾아서 알려드리겠습니다!

조금이라도 최적화를 할 수 있거나 다른 의견도 댓글에 남겨주세요!

지적과 비판 새로운 의견은 항상 환영합니다👍