https://www.acmicpc.net/problem/15990
15990: 1, 2, 3 더하기 5
각 테스트 케이스에 대해 n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나누고 나머지를 출력합니다.
www.acmicpc.net
정수 4를 1, 2, 3의 합으로 나타내는 세 가지 방법이 있습니다. 합계를 표현할 때 둘 이상의 숫자를 사용해야 합니다. 다만, 같은 번호를 연속으로 2회 이상 사용할 수 없다.
- 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로 나누고 나머지를 출력합니다.
해결 방법
배열을 적을 때 규칙을 보았습니다.
A(1)의 경우 1부터 시작하면 1, 2부터 시작하면 0, 3부터 시작하면 0 “1”
A(2) 1로 시작하면 0, 2로 시작하면 1, 3으로 시작하면 0 “2”
A(3)은 1부터 시작하면 1, 2부터 시작하면 1, 3부터 시작하면 1 “1 + 2” “2 + 1” “3”
이렇게 초기값을 설정하면
A(4)는 A(3) 앞에 1을 넣는다고 생각했다. 이를 해결하기 위해 A(3) = “1 + 2, 2 + 1, 3”, 앞에 1이 붙습니다.
A(4) = “1 + 1 + 2” , “1 + 2 + 1”, “1 + 3” 으로 생각하십시오.
그렇게 생각하면 1로 시작하고 앞서 A(3)에 표시된 것을 사용할 필요가 없습니다.
마찬가지로 A(2)는 시작 2를 사용하지 않고 A(1)은 시작 1을 사용하지 않고 조합을 만듭니다.
일반화하면 A(n) = A(n-1)이 1로 시작하지 않는 경우의 수, A(n-2)에서 2로 시작하지 않는 경우의 수, A(n )의 경우의 수 . -3) 3개의 의수로 시작하지 않는 것
따라서 다음과 같이 코드를 작성할 수 있습니다.
func sol() {
let target = Int(readLine()!)!
var checkArr:((Int)) = Array(repeating: (0), count: 100001)
checkArr(1) = (1, 0, 0)
checkArr(2) = (0, 1, 0)
checkArr(3) = (1, 1, 1)
let constVal = 1000000009
var flag = 4
for _ in 0...target - 1 {
let inputVal = Int(readLine()!)!
if checkArr(inputVal) == (0) {
for j in flag...inputVal {
checkArr(j) = ((checkArr(j - 1)(1) + checkArr(j - 1)(2)) % constVal, (checkArr(j - 2)(2) + checkArr(j - 2)(0)) % constVal, (checkArr(j - 3)(0) + checkArr(j - 3)(1)) % constVal)
flag += 1
}
}
print(checkArr(inputVal).reduce(0){$0 + $1} % constVal)
}
}
sol()
checkArr(j) = ((checkArr(j – 1)(1) + checkArr(j – 1)(2)) , (checkArr(j – 2)(2) + checkArr(j – 2)(0)) , (checkArr(j – 3)(0) + checkArr(j – 3)(1)))
이렇게 하면 이전 값을 알고 있으면 다음 값을 예측할 수 있습니다.