민망하지만..난 사실..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)
동전 문제는 정말 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;
}
'Algorithm 💫 > Problem Solving' 카테고리의 다른 글
[백준 11057번 오르막 수/ C++] (0) | 2021.01.07 |
---|---|
[백준 10844번 쉬운 계단 수/ C++](DP) (5) | 2021.01.07 |
[백준 2522번 별찍기 - 12/ C++] (0) | 2021.01.04 |
[백준 2445번 별찍기 - 8/ C++] (0) | 2021.01.04 |
[백준 2442번 별찍기 - 5/ C++] (0) | 2021.01.04 |
댓글