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

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

민망하지만..난 사실..dp에 굉.장.히. 약하다... 어떤 문제가 dp인지도 잘 판단하지 못하고 ㅠㅠㅠ 흑 그래서 이제 dp 문제를 좀 많이 풀어보려고 한다 헤헤 사실 약간 dp 에 감을 잡게된 문제는 동전! 문제인 것같다..ㅎㅅㅎ 갓동전....(https://ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%80-2293%EB%B2%88-%EB%8F%99%EC%A0%84-1-C?category=440812)

 

[백준 2293번 동전 1/ C++]

 

동전 문제는 정말 100% 이해하고 설명하고 싶다는 생각에 끝까지 이해하려고 노력했던 것 때문인지...! dp가 무엇을 하려는 건지 어떤 방식으로 접근하면 되는건지에 대한 감이 왔딸까...!!!!!!😮W0W

 

후 쨋든 처음 문제를 봤을때...이 문제를 어떻게 접근할까! 일단 써봤따...

index를 쓰고... 그 밑에는 각 index가 1 로 되기 위해 어떠한 연산을 몇 번 수행하는지 dp에 기록한다고 생각하며 규칙을 찾으려고 해보았다!

뭐 11정도까지 처음에 2와 3은 1로 지정해주고, 4부터 10정도까지 규칙을 찾아보니 아래와 같은 표를 만들 수 있었다. 

 

i	최소 연산 횟수	최소 연산 횟수가 나온 과정 (화살표 개수)	dp 식
2	1	2 -> 1	dp[2] = 1
3	1	3 -> 1	dp[3] = 1
4	2	4 -> 2 -> 1	dp[4] = 1+ dp[i / 2]
5	3	5 -> 4 -> 2 -> 1	dp[5] = 1+ dp[i - 1]
6	2	6 -> 3 -> 1 or  6 -> 2 -> 1	dp[6] = 1+ dp[i / 3] or dp[6] = 1+ dp[i / 2]
7	3	7 -> 6 -> 3 -> 1 or 7 -> 6 -> 2 -> 1	dp[7] = 1+ dp[i - 1]
8	3	8 -> 4 -> 2 -> 1	dp[8] = 1+ dp[i / 2]
9	2	9 -> 3 -> 1	dp[9] = 1+ dp[i / 3]
10	3	10 -> 9 -> 3 -> 1	dp[10] = 1+ dp[i - 1]
11	4	11 -> 10 -> 9 -> 3 -> 1	dp[11] = 1+ dp[i - 1]

 

우선 위의 과정에서 4가지의 줄기로 나누어 보았따!

1	i가 2 와 3으로 모두 나누어 떨어지지 않는 경우
2	i가 2와 3으로 모두 나누어 떨어지는 경우
3	i가 2로만 나누어 떨어지는 경우
4	i가 3으로만 나누어 떨어지는 경우

 

1. i가 2 와 3으로 모두 나누어 떨어지지 않는 경우

1번과 같은 경우는 "5, 7, 11" 등과 같은 숫자들인데 이러한 경우의 규칙은 명확히 보인다.

(i에서 1을 빼주는 을 해주는 연산 횟수 + i - 1의 숫자가 저장하고 있던 최소 연산 횟수) 를 해주면 된다. 

 

2. i가 2와 3으로 모두 나누어 떨어지는 경우

2번과 같은 경우 2로 나누어 연산을 수행하는 경우와 3으로 나누어 연산을 수행하는 경우 중 더 작은 값을 저장해주어야 한다. 우리는 최소 연산 횟수를 구해야하니까!!! 

그렇기 때문에 "6"과 같은 숫자는 2로 나누어 연산되는 과정과 3으로 나누어 연산되는 과정 중 min값을 넣어주면 된다 🐶

물론! 6이 나누어지는 과정 또한 더해야하니 +1!!!!

 

3. i가 2로만 나누어 떨어지는 경우

i가 2로만 나누어지는 과정은 "4, 8, 10" 등의 숫자들이 있다. 4와 8을 봤을 때는 i/2에 해당하는 값과 4와 8이 연산되는 횟수를 더해주면 될 것 같았지만!!!!!!!!!! 문제에서는 너무 친절하게 10의 연산 횟수가 나오는 과정이 "10 -> 9 -> 3 -> 1"이라고 말해줬따...흠 그럼 2로 나눈 곳에서 가져온 연산이 아닌데!!

만약 i/2를 해서 연산횟수를 가져왔다면 dp[5] + 1이 됐을 터인데...dp[5] + 1 = 4 이다..흠! 하지만 i - 1의 연산횟수인 dp[9]와 1을 더해주면  3 이기 때문에 ㅎㅎ더 작은 쪽을 선택한 것이다. 그럼 저 둘 중 더 작은 값을 넣으면 되겠찌?

 

4.  i가 3으로만 나누어 떨어지는 경우

자 3번과 같은 과정이다 헿 3으로 나누어 떨어지는 경우만 고려하는 것이 아니라 i - 1 의 경우가 더 작을 수도 있다는 점을 고려해서 min 값을 넣어쥬자!

 

그럼 코드는 다음과 같이 나온다 ㅎㅅㅎ 사실 dp 가 아직 익숙하지 않아서...! 차차 익숙해져보기로 하쟈 🙏

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> dp(1000001, 0);
int main()
{
    int N;
    cin >> N;

    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;

    for (int i = 5; i <= N; i++) {
        if (i % 2 != 0 && i % 3 != 0)
            dp[i] = dp[i - 1] + 1;
        else if (i % 2 == 0 && i % 3 == 0)
            dp[i] = min(dp[i / 2] + 1, dp[i / 3] + 1);
        else if (i % 2 == 0)
            dp[i] = min(dp[i / 2] + 1, dp[i - 1] + 1);
        else if (i % 3 == 0)
            dp[i] = min(dp[i / 3] + 1, dp[i - 1] + 1);
    }
    cout << dp[N];

    return 0;
}