[BOJ][9095번] - 1,2,3 더하기

안녕하세요 Dibrary입니다.

이번에는 제가 개인적으로 어려워해서 푸는데 시간이 꽤나 걸린 동적프로그래밍 문제를 풀어보겠습니다.

지금도 까딱하면 동적프로그래밍 '감'을 잃을거 같아서 조심스럽네요...

 

문제는 아래와 같습니다.

 

처음에 이 문제를 보자마자 어디서 '생각'이 멈췄냐면

• 1을 쓰는 것과 2를 쓰는 것의 '순간'을 어떻게 알지?
• 2 외에 3이 있다다는 것을 어떻게 알지?

이런 생각 때문에 문제를 못 풀었습니다...

 

그래서 그냥 하염없이 갯수를 세다가 문득 규칙성이 보이길래 좀 더 해봤습니다.

제가 이렇게 '규칙성을 찾아서 문제를 풀어야 한다'는 개념을 알게 된 문제는 아래 문제였습니다.

20500번: Ezreal 여눈부터 가네 ㅈㅈ

(이 문제 풀이를 이해하셨다면 위 문제도 도전해보시길 권합니다.)

 

먼저 그냥 손으로 막 써보면 아래와 같습니다.

1은 1만 가능하므로 1개.
2는 1+1, 2가 가능하므로 2개.
3은 1+1+1, 1+2, 2+1, 3이 가능하므로 4개.
4는 문제의 예제에 나온 수 7개.
5는 갯수를 세 보면 13개가 나옵니다.

뭔가 규칙성이 보이지 않나요? 

4는 1+2+4를 한 7개이고
5는 2+4+7을 한 13개가 됩니다.

 

그러면 1, 2, 3 번째만 채워 넣고 나머지는 계속 더해 나가면 되겠구나! 싶은 생각이 들죠. 

코드는 간단합니다. 

처음에 1,2,3을 tb라는 리스트에 넣어두고, for문으로 나머지를 채워준 후에 그저 입력값을 index로 보내면 됩니다.

 

잘 보시면 tb를 12개 까지만 만들어 놓았는데, 그 이유는 문제에서 주어지는 숫자가 11까지라고 되었기 때문에 사실 그 이후의 숫자에 대한 여분을 만들 필요가 없기 때문입니다.