https://www.acmicpc.net/problem/10844
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.lang.StringBuilder val br = BufferedReader(InputStreamReader(System.`in`)) val bw = BufferedWriter(OutputStreamWriter(System.out)) val n = readLine()!!.toInt() val graph = Array(n+1,{IntArray(10)}) fun main()=with(br) { for (i in 1..9) { graph[1][i] = 1 } val mod = 1000000000 for (i in 2..n) { for (j in 0..9) { when (j) { 0 -> { graph[i][j] = graph[i - 1][j + 1] % mod } 9 -> { graph[i][j] = graph[i - 1][j - 1] % mod } else -> { graph[i][j] = (graph[i - 1][j - 1] + graph[i - 1][j + 1]) % mod } } } } var ans = 0 // for(i in 1 .. n){ // for(j in 0 until 10){ // bw.write("${graph[i][j]}") // } // bw.write("\n") // } for (i in 0 until 10) { ans += graph[n][i] ans %= mod } bw.write("$ans") bw.flush() bw.close() } | cs |
'알고리즘 공부 > DP' 카테고리의 다른 글
백준 12865번 평범한 배낭 with Kotlin (0) | 2021.09.07 |
---|---|
백준 11054번 가장긴 바이토닉 부분 수열 with Kotlin (0) | 2021.09.06 |
백준 9465번 with Kotlin (0) | 2021.09.01 |
백준1912번 with Kotlin (0) | 2021.08.25 |
백준 1932번 with Kotlin (0) | 2021.08.21 |