[BOJ] 백준 1463 1로 만들기 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

💣 문제 이해

 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

4, 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 이용하여 1을 만들고자 한다.

 

이때, 필요한 연산 횟수의 최소값을 구하는 것이 목표이다.

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

💭 풀이 과정

 

바텀업(Bottom-Up) 방식으로 구현했다. (다른 분들 풀이를 보니, 탑다운 방식도 있고 다양했다.. 나빼고 다천재인듯...)

입력 값의 최대가 10⁶ (1,000,000) 이므로 크기가 100만이고 각 원소를 100만으로 초기화한 int 형 벡터를 사용했다.

벡터 내부 각 원소는 그 인덱스 번호에 해당하는 숫자의 연산 횟수를 값으로 가지고 있다.

(map[i]는 현재 기준 숫자 i의 연산 횟수)

 

i번째 인덱스부터 진행하면서 i+1, i*2, i*3 의 기존 연산 횟수보다 더 작은 경우 대체하는 방식이다.

결과적으로 map 벡터에는 각 인덱스 번호에 해당하는 숫자의 최소 연산 횟수가 기록된다.

 

작성 언어: C++

 

#include <cstdio>
#include <vector>
using namespace std;

int main(){
    int num = 0;
    vector<int> map(1000001, 1000000);
    map[0] = 0;
    map[1] = 0;
    // map[i]는 현재 기준 숫자 i의 연산 횟수
    for (int i = 1; i < map.size(); ++i) {
        int operCnt = map[i] + 1;   // 현재 숫자의 연산 횟수에 1을 더함(+1, *2, *3 모두 연산을 한 번 더 하는 것이므로)
        /********* +1 하는 경우 *********/
        // i+1의 기존 연산 횟수보다 더 작은 경우 대체
        if(i+1 <= map.size() && operCnt < map[i+1])  map[i+1] = operCnt;
        /********* *2 하는 경우 *********/
        // i*2의 기존 연산 횟수보다 더 작은 경우 대체
        if(i*2 <= map.size() && operCnt < map[i*2])  map[i*2] = operCnt;
        /********* *3 하는 경우 *********/
        // i*3의 기존 연산 횟수보다 더 작은 경우 대체
        if(i*3 <= map.size() && operCnt < map[i*3])  map[i*3] = operCnt;
    }
    scanf("%d", &num);
    printf("%d\n", map[num]);
    return 0;
}

 

 

🏆 배운 점

 

DP 문제 풀이의 시작이다..!

 

열씨미 해봐야겠다!!! 🐶