문제 링크
기초 DP 문제 중 하나입니다.
저도 DP를 잘 몰라서 감을 잡아가는 동안 푸는 문제였죠.
우선 DP에서 가장 중요한게 메모이제이션이라고 생각하지만 규칙을 찾아야 메모이제이션이 가능하다고 볼 수 있죠.
그래서 이번 문제를 해결하면서 규칙을 찾는 과정을 어떻게 생각해내느냐를 좀 더 중점적으로 공부했습니다.
우선 문제를 보고 뭐든 손으로 값을 구해봐야 하겠죠?
아무것도 모르면 규칙을 알 수 없으니까요.
그렇게 구하다보면
1-> 1개
2-> 2개
3-> 4개
4-> 7개
5-> 13개
6-> 24개
7-> 44개
...
이렇게 나오게 됩니다. 한번씩 7까지는 손으로 해보시는 걸 추천드립니다.
이 문제는 사실 11보다 작은 수만 입력값으로 들어오기 때문에 일일이 하나씩 구해도 문제는 없습니다.
하지만 그러면 DP를 공부하는 의미가 없겠죠?
일단 위의 갯수들을 구해도 뭐 어쩌라는건지 알 수 없습니다.
DP를 많이 풀어봤다면 규칙을 찾을 수 있겠지만 저는 초보기 때문에 잘 모릅니다.
일단 DP의 가장 기본!
"앞의 값들로 뒤의 값을 구한다"
이니까요. 한번 구해봅시다. 1 하나만 보게되면 3까지는 x2를 해주면 되네요.
근데 그 다음부터는 규칙이 성립하지 않죠. x2 + 1, x2 - 1 등 규칙이라고 볼 수 없는 수식들이 등장합니다.
그러니까 이건 제외하고, 1과 2를 같이 봅시다. [1] + [2] + 1을 해주면 [3]의 값인 4가 나오고, [2] + [3] + 1을 해주면 [4]의 값인 7이 나옵니다.
오 꽤괜이죠?
[3] + [4] + 1의 값은 12네요. 아쉽게 하나가 모자랍니다.
[4] + [5] + 1은 20이니까 4가 모자르죠. 꽤괜은 무슨 안됩니다.
이제 남은 방법은
- 2, 3을 같이 본다.
- 1, 3을 같이 본다.
- 1, 2, 3을 같이 본다.
입니다.
[1, 3]은 그냥 눈대중으로 봐도 아니죠? 암산으로 잠깐 해봐도 규칙이 나오지 않아보입니다.
[2, 3]은 [1, 2]와 사실 다를게 없죠. 그러니까 아니라는 것을 확신하고 넘어가줍니다.
1, 2, 3을 같이 본다.
여기까지 오면 제 생각의 흐름을 따라오고 계신겁니다.
생각의 흐름대로 적는거라 중구난방이지만 저 사람은 이렇게 생각하는구나를 보여줄 수 있어서 좋을 것 같습니다.
자 마지막으로 [1] + [2] + [3]을 더해봅시다. 그럼 [4]의 값이 나오죠?
[2] + [3] + [4]의 값을 더하면? 놀랍게도 5의 값이 나옵니다.
근데 꼴랑 두개 맞았다고 규칙이다! 라고 하진 않으시겠죠?
위에서도 2개는 맞는게 있었으니까요. 더 해봅시다.
[3] + [4] + [5] = 24
[4] + [5] + [6] = 44
오 진짜 되네요.
그럼 이제 이걸 코드로 작성해봅시다.
코드
#include <iostream>
using namespace std;
int main (int argc, char *argv[]) {
int n;
int dp[11];
int i;
int a;
cin >> n;
dp[0] = 1;
dp[1] = 2;
dp[2] = 4;
i = 3;
while (i < 11) {
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
i++;
}
i = 0;
while (i < n) {
cin >> a;
cout << dp[a - 1] << "\n";
i++;
}
return 0;
}간단하게 생각나는대로 작성해본 코드입니다.
여기까지 하면 문제는 해결됩니다.
최적화
여기서부터는 제 나름대로의 최적화를 진행해보는 부분입니다.
[추후 업데이트]
