[BOJ][C++] 백준 15990번 1, 2, 3 더하기 5
Updated:
15990번 1, 2, 3 더하기 5
1. 문제 정보
백준 온라인 저지 [15990번 1, 2, 3 더하기 5] 문제의 링크입니다.
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
- 1+2+1
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
예제 입력1
3
4
7
10
예제 출력1
3
9
27
시간 / 메모리 제한
1초 / 256MB
2. 생각
- 문제 9095번 1, 2, 3 더하기와 비슷한 문제입니다. 문제 9095번과 다른 점은 문제 9095번 보다 제약조건이 추가된 것입니다. 그 제약조건은 바로 이전에 사용한 숫자는 사용할 수 없는 것입니다.
-
문제 15990번도 문제 9095번 처럼 큰 문제를 작은 문제로 쪼갤 수 있고, 작은 문제의 해답을 합쳐 큰 문제의 답을 풀 수 있기 때문에 동적계획법으로 풀고 Bottom-up 방식으로 풀겠습니다.
-
문제 9095번의 dp 배열은 n을 1, 2, 3의 합으로 나타내는 방법의 수로 정의했습니다.
하지만, 바로 이전에 사용한 숫자를 그 다음에 사용하지 못한다는 제약조건이 추가된 문제 15990번은 바로 이전에 더하는 데에 1을 사용했는지, 2를 사용했는지, 3을 사용했는지 체크하여 경우를 나눠야합니다. -
따라서 dp배열을 2차원으로 사용하겠습니다. dp[n][1], dp[n][2]. dp[n][3]을 활용할 것입니다.
dp[n][1]은 n을 만드는데 1을 더할 것이고, 이전(dp[n-1])에 1을 사용하지 않았다는 뜻입니다.
2를 더할 때는 전전(dp[n-2]), 3을 더할 때는 전전전(dp[n-3]) 배열을 고려해야합니다. - 결론적으로, 1을 더할 때는 dp[n-1][2]에 1을 더하고(이전에 2를 더했음), dp[n-1][3]에 1을 더한 것을(이전에 3을 더했음) 합치면 됩니다.
그것을 확장하여 식으로 나타내면
dp[n][1] = dp[n-1][2] + dp[n-1][3]
dp[n][2] = dp[n-2][1] + dp[n-2][3]
dp[n][3] = dp[n-3][1] + dp[n-3][2] 으로 나타낼 수 있습니다.
이를 1,000,000,009로 나누어 저장합니다.
- 마지막으로는 1을 더해서 만든 가짓수, 2를 더해서 만든 가짓수, 3을 더해서 만든 가짓수 모두 합치면 원하는 n을 1, 2, 3을 더해서 만든 가짓수가 나옵니다.
dp[n][1] + dp[n][2] + dp[n][3]
- 여기서 조심할 점이 있습니다. 저는 공간을 절약하기 위해 long long 자료형을 쓰지 않고 int 자료형으로 dp 배열을 사용했습니다. int 자료형은 약 21억정도의 수를 저장할 수 있는데, dp[n][1] 하나가 최대 10억 8의 수를 가질 수 있습니다. 따라서 셋을 더하면 약 30억이므로 int 자료형이 표현할 수 있는 범위를 초과합니다. 그래서 반드시 합할 때는 long long 자료형으로 형변환을 해야합니다.(여기서 여러번 틀렸습니다…ㅠㅠ)
- 참고
dp 배열
i\j 1 2 3 합 1 1 0 0 1 2 0 1 0 1 3 1 1 1 3 4 2 0 1 3 5 1 2 1 4 6 3 3 2 8 7 5 2 2 9
3. 소스코드 (C++)
