안녕하세요 Dibrary입니다. 이번에는 제가 개인적으로 어려워해서 푸는데 시간이 꽤나 걸린 동적프로그래밍 문제를 풀어보겠습니다. 지금도 까딱하면 동적프로그래밍 '감'을 잃을거 같아서 조심스럽네요... 문제는 아래와 같습니다. 처음에 이 문제를 보자마자 어디서 '생각'이 멈췄냐면 1을 쓰는 것과 2를 쓰는 것의 '순간'을 어떻게 알지? 2 외에 3이 있다다는 것을 어떻게 알지? 이런 생각 때문에 문제를 못 풀었습니다... 그래서 그냥 하염없이 갯수를 세다가 문득 규칙성이 보이길래 좀 더 해봤습니다. 제가 이렇게 '규칙성을 찾아서 문제를 풀어야 한다'는 개념을 알게 된 문제는 아래 문제였습니다. 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출..