728x90
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
풀이
- 피보나치 수열을 재귀를 이용하여 풀 경우 시간 초과가 발생한다.
- 동적 프로그래밍(dp) 알고리즘을 이용하여 시간 초과를 해결 한다.
- 2차원 Int 배열을 선언한다.
- dp[n][0] 에 0이 나오는 횟수를 저장한다.
- dp[n][1] 에 1이 나오는 횟수를 저장한다.
코드
import java.util.*
private val dp = Array(41) { IntArray(2) }
fun main(args: Array<String>) {
val sc = Scanner(System.`in`)
val T = sc.nextLine().toInt()
// 초기 dp 값
dp[0][0] = 1 // n이 0일 때 0의 횟수
dp[1][1] = 1 // n이 1일 때 1의 횟수
repeat(T) {
val n = sc.nextLine().toInt()
for (i in 2..n) {
dp[i][0] = dp[i - 1][0] + dp[i - 2][0]
dp[i][1] = dp[i - 1][1] + dp[i - 2][1]
}
// 결과 출력
println("${dp[n][0]} ${dp[n][1]}")
}
}
728x90
'알고리즘' 카테고리의 다른 글
[백준][KOTLIN] 1904 01타일 (0) | 2021.12.09 |
---|---|
[백준][KOTLIN] 9184 신나는 함수 실행 (0) | 2021.12.08 |
[백준][KOTLIN] 18870 좌표 압축 (0) | 2021.12.08 |
[백준][KOTLIN] 10814 나이순 정렬 (0) | 2021.12.07 |
[백준][KOTLIN] 1181 단어 정렬 (0) | 2021.12.07 |