[BOJ][C++] 백준 15988번 1, 2, 3 더하기 3
Updated:
15988번 1, 2, 3 더하기 3
1. 문제 정보
백준 온라인 저지 [15988번 1, 2, 3 더하기 3] 문제의 링크입니다.
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
예제 입력1
3
4
7
10
예제 출력1
7
44
274
시간 / 메모리 제한
1초 / 256MB
2. 생각
- 문제 9095번 1, 2, 3 더하기와 문제 15990번 1, 2, 3 더하기 5와 매우 유사한 문제입니다. 이 문제 15990번은 제약조건이 달라졌었지만, 현재 문제인 문제 15988번 문제는 문제 9095번 1, 2, 3 더하기 문제와 조건은 똑같고 입력의 크기가 달라진 것이 차이점입니다. 따라서 문제 9095번의 코드를 활용할 것이므로 아래의 문제 9095번의 풀이도 참고해주세요.
-
입력의 크기가 최대 10에서 1,000,000으로 커졌습니다. 코드의 점화식을 보면 피보나치 수와 유사하지만 i-3의 값도 더하기 때문에 이 점화식이 피보나치의 점화식보다 더 급격하게 커집니다. 따라서 1,000,000,009로 나누어 저장하여 저장되는 수의 범위를 제한합니다.
-
dp 배열에 저장되는 각각의 수는 십억까지의 수가 저장되지만 그 수끼리 더하는 과정이 있으므로 int의 수의 표현 범위인 21억 정도의 수를 넘어갈 수 있습니다. 따라서 자료형을 long long을 사용합니다.
-
그리고 크기가 백만이 넘어가는 배열은 main 함수의 스택에 쌓이기 어렵습니다. 따라서 전역 공간에 생성하여 다른 메모리 영역에 선언해줍니다.
- 테스트 케이스의 수만큼 반복되는 과정이므로 n을 입력 받기 전에 dp배열은 0부터 최대 값 1,000,000까지 값을 가지고 시작합니다. 그러면 n을 입력받으면서 바로 출력할 수 있습니다.
3. 소스코드 (C++)
