문제
정수 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
Plain Text
복사
예제 출력 1
3
9
27
Plain Text
복사
My solution
1,2,3 더하기 4
1) 4를 만들 수 있는 수식 중에서, 1로 끝나는 수식은 3을 만드는 수식에서 1을 더하는 것이다.
즉, dp[4][1] = dp[3][1]이다. 일반화하면, dp[n][1] = dp[n-1][1] 이다.
2) 4를 만들 수 있는 수식 중에서, 2로 끝나는 수식은 2를 만드는 수식에서 1로 끝나는 것과 2로 끝나는 것에 2를 더하는 것이다.
즉, dp[4][2] = dp[3][2] + dp[3][1]이다. 일반화하면, dp[n][2] = dp[n-2][1] + dp[n-2][2] 이다.
3) 4를 만들 수 있는 수식 중에서, 3으로 끝나는 수식은 1를 만드는 수식에서 1, 2, 3으로 끝나는 것에 3을 더하는 것이다.
즉, dp[4][3] = dp[1][1] + dp[1][2] + dp[1][3] 이다.
(물론, 1은 2나 3으로 끝나는 경우가 없으므로, dp[1][2] = 0, dp[1][3] = 0이다.)
일반화하면, dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][3] 이다.
위와 같은 과정을 통해
dp[i][1] = dp[i-1][1];
dp[i][2] = dp[i-2][1] + dp[i-2][2];
dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]; (n >= 4)라는 점화식이 나온다.
1,2,3 더하기 5
필요한 조건 2가지
1.
N을 만들기 위한 경우의 수
2.
그 수식의 마지막이 어떤 수로 끝나는지(연속되면 안되기 때문에)
7을 1, 2, 3의 합으로 나타내는 경우의 수를 살펴보자.
1.
7을 만드는 수식 중 마지막이 1로 끝나는 것의 수
- 6을 만드는 수식 중 마지막이 2로 끝나는 것 + 1
- 6을 만드는 수식 중 마지막이 3로 끝나는 것 + 1
DP[7][1] = DP[6][2] + DP[6][3]
2.
7을 만드는 수식 중 마지막이 2로 끝나는 것의 수
- 5를 만드는 수식 중 마지막이 1로 끝나는 것 + 2
- 5를 만드는 수식 중 마지막이 3로 끝나는 것 + 2
DP[7][2] = DP[5][1] + DP[5][3]
3.
7을 만드는 수식 중 마지막이 3로 끝나는 것의 수
- 4를 만드는 수식 중 마지막이 1로 끝나는 것 + 3
- 4를 만드는 수식 중 마지막이 2로 끝나는 것 + 3
DP[7][3] = DP[4][1] + DP[4][2]
위 세 경우를 일반화하면 다음의 점화식이 나온다.
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]
반복하는 횟수는 테스트케이스당 한번만 해야 시간초과가 나지 않으므로 처음에 max를 구해서 DP 배열을 미리 구성해놓은 다음 테스트케이스에 맞는 답을 구한다.
스터디원 풀이
RGB 거리같은 문제
const [N, ...input2] = i.toString().trim().split('\n');
const arr = input2.map(v => v.split(' ').map(Number));
for (let i = 1; i < N; i++) {
arr[i][0] += Math.min(arr[i - 1][1], arr[i - 1][2]);
arr[i][1] += Math.min(arr[i - 1][0], arr[i - 1][2]);
arr[i][2] += Math.min(arr[i - 1][0], arr[i - 1][1]);
}
console.log(Math.min(...arr[N - 1]));
JavaScript
복사
DP는 0번인덱스 안쓰고 1~3이므로 length를 4로 줘서 만듦
const DP = Array.from({ length: max + 1 }, () =>
Array.from({ length: 4 }, () => 0)
);
JavaScript
복사
1만드는 건?
1뿐
2만드는 건?
앞에 1이 오면 연속된 1이 나와야하므로 어차피 안되고, 앞에 3이 오면 2를 만들 수 없으므로 안된다.
원래는
연속된 숫자가 올 수 없으므로 위와 같이 하지 못한다. 그래서 dp가 2차원 배열이 되고 1,2,3으로 나누어 할당한 뒤 경우의 수를 구해야만 한다.
Code
const solution = function (i) {
const [T, ...tcArr] = i.toString().trim().split('\n').map(Number);
let result = '';
// 시간 초과 방지
const max = Math.max(...tcArr);
const DP = Array.from({ length: max + 1 }, () =>
Array.from({ length: 4 }, () => 0)
);
DP[1][1] = 1; // 1을 만드는 수식 중 마지막이 1로 끝나는 경우의 수
DP[2][2] = 1; // 2를 만드는 수식 중 마지막이 2로 끝나는 경우의 수
DP[3][1] = 1; // 3을 만드는 수식 중 마지막이 1로 끝나는 경우의 수
DP[3][2] = 1; // 3을 만드는 수식 중 마지막이 2로 끝나는 경우의 수
DP[3][3] = 1; // 3을 만드는 수식 중 마지막이 3으로 끝나는 경우의 수
for (let i = 4; i <= max; i++) {
DP[i][1] = (DP[i - 1][2] + DP[i - 1][3]) % 1000000009;
DP[i][2] = (DP[i - 2][1] + DP[i - 2][3]) % 1000000009;
DP[i][3] = (DP[i - 3][1] + DP[i - 3][2]) % 1000000009;
}
for (const tc of tcArr) {
result += ((DP[tc][1] + DP[tc][2] + DP[tc][3]) % 1000000009) + '\n';
}
console.log(result.substring(0, result.length - 1));
return result.substring(0, result.length - 1);
};
describe('1,2,3 더하기 5', () => {
it('TC1', () => {
expect(
solution(`3
4
7
10`)
).toStrictEqual(`3
9
27`);
});
});
JavaScript
복사
