[백준 1463번] 1로 만들기

🔗알고리즘 문제

dp에 대해 익숙하지 않을 때 마주하게 된 dp문제이다,, 지금까지 dp문제를 풀어본 경험이 거의 없어 문제의 접근부터 굉장히 어려웠다. 이 문제를 계기로 dp에 대한 공부가 된 것 같아 나름 보람찬 문제였다.

문제 분석

이 문제는 단순히 정수 X가 입력으로 주어졌을 때 정수 X에 대해 세가지 연산을 적절히 수행하며 1이 되는 최소 경로를 구하는 문제이다.

1. X가 3으로 나누어 떨어질 경우 3으로 나누기
2. X가 2로 나누어 떨어질 경우 2로 나누기
3. 1빼기

예를 들어 10이라는 X가 주어졌을 때 다음과 같은 과정을 거쳐 정답을 출력하게 된다.

X : 10

9 <- 1을 빼기
3 <- 3으로 나누기
1 <- 3으로 나누기

3번만에 1이 됨

정답으로 3이 출력되게 된다.

발상

처음에는 이 문제가 dp란 것에 집중하여 dp로 해결할 수 있는 규칙성을 찾는데 시간을 많이 허비했던 것 같다,,

그러던 중 1부터 X까지 최소경로를 작성해 본 표에서 규칙을 찾을 수 있었다.

1	2	3	4	5	6	7
0	1	1	2	3	2	3

8	9	10	11	12	13	14
3	2	3	4	3	4	4

이 표를 배열이라고 생각하였을 때

1. index가 3으로 나누어 떨어지면 최소경로는 array[index/3] + 1이 된다.

2. index가 2로 나누어 떨어지면 최소경로는 array[index/2] + 1이 된다.

3. 만약 index가 3, 2 둘 중 하나로도 나누어 떨어지지 않는다면
최소경로는 array[index - 1] + 1이 된다.

이러한 3가지 규칙을 찾을 수 있었다.

찾아낸 규칙에 따라 로직을 작성하여 문제를 해결하기로 하였다.

알고리즘 설계

1. n을 입력받기
2. 2부터 n까지 for문을 돌며 dp에 값을 채우기
   • dp[index]에는 기초값으로 index가 3, 2 둘 중 하나로도 나누어 떨어지지 않는 경우의 최소경로가 담겨있다
   • 만약 index가 3으로 나누어 떨어진다면 현재 dp의 들어있는 값과 3으로 나누었을 경우의 최소경로 중 최소값을 dp에 넣는다.
   • 만약 index가 2로 나누어 떨어진다면 현재 dp의 들어있는 값과 2로 나누었을 경우의 최소경로 중 최소값을 dp에 넣는다.
3. dp에 n값 출력한다.

코드

#include<iostream>

using namespace std;

int main(){
    int dp[1001] = {};

    int num;
    int temp;

    cin >> num;

    for(int i = 2; i <= num; i++){
        dp[i] = 1 + dp[i - 1];

        if(i % 3 == 0)
            dp[i] = min(1 + dp[i / 3], dp[i]);
        if(i % 2 == 0)
            dp[i] = min(1 + dp[i / 2], dp[i]);
    }

    cout << dp[num];
}