문제 링크 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N) - 1,2,3 더하기 문제에서 조금 변형된 문제, 상향식, 하향식 연습하기 좋은 문제 - 단, 같은 숫자를 연속적으로 붙일 수 없기 때문에 이전 숫자에서 무엇이 사용되었는지 상태값을 기록할 필요가 있다 (2차원 배열 사용) - 간단하게 2차원 배열로 해서 1 ~ 3 숫자 사용 여부를 표기하고 동일하게 점화식으로 구하면 됨 - 최대치 long DP[N + 1][4] 2차원 배열 생성 ( DP[N][1..