[BOJ][DP]9005 1,2,3 더하기
https://www.acmicpc.net/problem/9095 이 문제는 규칙을 파악하는 문제다. 필자도 아무리 생각해도 갈피를 못 잡아 인터넷 참고를 조금 했다. - 풀이 - n = 1 일때, ( 1 )로, 경우의 수는 1개.n = 2일때, (1 + 1), ( 2 )로, 경우의 수는 2개.n = 3일때, (1 + 1 + 1), (1 + 2), (2 + 1), ( 3 )으로 경우의 수는 4개. n = 4는 문제 예시에 나와있으므로 7개. 어라? n = 1~3 까지의 경우를 더한게 n = 4의 경우의 수랑 같네? 위의 사실로는 n[i] = n[i-3] + n[i-2] + n[i-1] 과 같다. 우연일지도 모른다. 그래서 일단 위의 가설을 전제로 n = 7까지 계산해보자. n = 5, 13개 n = 6,..