https://www.acmicpc.net/problem/9625
9625번: BABBA
상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했
www.acmicpc.net
난이도 : 실버 5
태그 : 다이나믹 프로그래밍
설명
규칙을 찾아 풀 수 있는 다이나믹 프로그래밍 문제입니다.
| 회차 | 문자열 | A | B |
| 0 | A | 1 | 0 |
| 1 | B | 0 | 1 |
| 2 | BA | 1 | 1 |
| 3 | BAB | 1 | 2 |
| 4 | BABBA | 2 | 3 |
| 5 | BABBABAB | 3 | 5 |
회차가 오를 때마다,
A는 이전 회차의 B,
B는 이전 회차의 A + B의 값과 같습니다.
즉 A[i] = B[i-1] (i > 0, A[0] = 1)
B[i] = A[i-1] + B[i-1] (i > 0, B[0] = 1) 으로 나타낼 수 있습니다.
소스코드
fun main() {
val k = readln().toInt()
val dpA = Array(k + 1) { 0 }
val dpB = Array(k + 1) { 0 }
dpA[0] = 1
dpB[0] = 0
dpA[1] = 0
dpB[1] = 1
for (i in 1..k) {
dpA[i] = dpB[i - 1]
dpB[i] = dpA[i - 1] + dpB[i - 1]
}
println("${dpA[k]} ${dpB[k]}")
}
위에서 구한 점화식을 코드로 그대로 나타내면 됩니다.
후기
회차에 따라 하나씩 값을 구하면서 규칙을 찾아 풀 수 있는 문제였습니다.
'코딩테스트 > Kotlin' 카테고리의 다른 글
| [백준 2193번] [Kotlin] 이친수 (0) | 2022.11.24 |
|---|---|
| [백준 13699번] [Kotlin] 점화식 (0) | 2022.11.24 |
| [백준 5789번] [Kotlin] 한다 안한다 (0) | 2022.11.23 |
| [백준 3182번] [Kotlin] 한동이는 공부가 하기 싫어! (0) | 2022.11.18 |
| [백준 1388번] [Kotlin] 바닥 장식 (0) | 2022.11.18 |
