Kotlin/Algorithm Problems
<백준> 1, 2, 3 더하기 4(Gold 5)
re트
2024. 4. 2. 11:33
728x90
[백준]
https://www.acmicpc.net/problem/15989
[깃허브]
이 더하기 문제는 매번 볼 때마다 막히는 거 같다...
4번째 시리즈이길래 전에 다른 시리즈를 풀었나 확인해보니까 푼 것이 있었고 코드를 보는데 이해가 안 되더라...ㅎ
이번에는 잘 뚫기 위해 노력했는데 잘 기억하고 있어야겠다.
먼저 이런 문제는 어딘가 하나를 고정하는게 필요한 거 같다.
특히 이 문제는 1,2,3만을 사용할 수 있고 순서만 다른 수열은 같은 수열로 취급하기 때문에 가장 오른쪽 숫자를 고정하는 방식을 취했다.(사실 이런 문제들은 다 그렇게 하는 거 같기도 하다.)
가장 쉬운 문제에서 일반적인 방식으로 할 때 문제의 해결 점화식은 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] (i >= 4) 인데 순서가 섞인 것도 포함한 것이기 때문에 그걸 제외하기 위해 오름차순인 수열만 포함시켜야한다.
가장 오른쪽 숫자를 고정하면 1 앞에는 1만 와야하고 그 앞에 오는 숫자는 현재 숫자보다 1 작은 숫자여야한다.
2 앞에는 1이나 2가 마지막인 오름차순인 수열이 와야하고 그 앞에 오는 숫자는 현재 숫자보다 2 작은 숫자여야한다.
3 앞에는 1이나 2, 3이 마지막인 오름차순인 수열이 와야하고 그 앞에 오는 숫자는 현재 숫자보다 3 작은숫자여야한다.
위의 조건을 코드로 만들기 위해 2차원 배열을 사용하게 된다.
앞의 괄호는 숫자가 들어가고 뒤의 괄호는 마지막 숫자가 1,2,3 중에 어떤 것인지를 알려준다.
예를 들어, dp[5][2]는 5에서 마지막이 2로 끝나는 오름차순 수열의 개수이다.
여기서 기본으로 알 수 있는 정보는 다음과 같다.
dp[1][1] = 1 ← 1
dp[2][1] = 1 ← 1 1
dp[2][2] = 1 ← 2
dp[3][1] = 1 ← 1 1 1
dp[3][2] = 1 ← 1 2
dp[3][3] = 1 ← 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]
해당 방법으로 작성한 코드는 다음과 같다.
fun main() = with(System.`in`.bufferedReader()) {
val t = readln().toInt()
val dp = Array(10001) { Array(4) { 0 } }
dp[1][1] = 1
dp[2][1] = 1
dp[2][2] = 1
dp[3][1] = 1
dp[3][2] = 1
dp[3][3] = 1
for (i in 4..10000) {
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]
}
repeat(t) {
val n = readln().toInt()
println(dp[n][1] + dp[n][2] + dp[n][3])
}
}
참고)
반응형