15988 1, 2, 3 더하기 3

15988 1, 2, 3 더하기 3 / c++ / Silver2 / 39분

문제 및 코드

접근 방식

동적 프로그래밍

1. N=4 일 때, 두 수의 합이 4인 경우를 구해보면
   1. 1 + 3
   2. 2 + 2
   3. 3 + 1
2. 여기서 뒤의 수가 1보다 크면 1번 공식을 재귀적으로 적용할 수 있다.
   1. 1 + 3
      1. 1 + 1 + 2
         1. 1 + 1 + 1 + 1
      2. 1 + 2 + 1
   2. 2 + 2
      1. 2 + 1 + 1
   3. 3 + 1
3. 찾은 규칙은, 뒤의 수가 1보다 클 경우, 재귀적으로 다시 쪼갤 수 있다는 점이고, 이는 당연히 저장해두면 부수적인 계산을 하지 않아도 되므로 DP를 활용할 수 있다.
4. 최종적으로 구하는 식은 DP[N] = DP[N-1] + DP[N-2] + DP[N-3] (N > 3) 이었다. (선형적인 구조이므로, 이렇게 계산하면 시간과 메모리 효율이 훨씬 좋아진다.)

다시 생각해 볼 점

1. 처음엔 (제목에도 나와있는데) 1, 2, 3 만을 가지고 숫자를 표현하는 줄 모르게, 해당 숫자를 표현하는 모든 경우의 수를 구하는 줄 알았다. (역시나 꼼꼼히 문제를 읽지 못한 잘못이다.)
2. 계산식에서 뒤에 오는 수를 DP를 활용하려는 시도는 좋았다고 생각한다. 하지만 그 점화식으로 접근 방식에서 4번의 식을 발견하지 못했다. 그래서 메모리와 시간을 다른 제출들 대비 엄청 잡아먹었는데, 다른 사람들의 풀이와 질문 게시판을 보고서야 4번의 식을 유추할 수 있었다.
3. 놓지말고 알고리즘은 꾸준히 풀어야겠다.