문제 이해 & 기본 개념
- 계단은 1~2칸 씩 이동할 수 있다.
- 3칸을 연속으로 밟아선 안된다.
- 마지막 계단은 반드시 밟아야한다.
위의 조건에 한해서 계단을 밟았을 때 받을 수 있는 가장 높은 점수를 구하는 문제
중요 포인트
해당 문제에서의 중요 포인트는 아래와 같다.
- 맨 뒤에서부터 시작
- 문제 조건에서 마지막 계단은 무조건 밟아야한다고 명시되어 있다.
- 시작점을 마지막 계단으로 놓고 내려가는 방식으로 구현하면 쉽다.
- 연속으로 3개의 계단을 밟는 경우 판별
- 이전에 몇 칸을 뛰어서 왔는지를 알면 연속으로 3칸을 밟는지 쉽게 확인할 수 있다.
- 이전에 1칸만 뛰어서 온 경우라면 이번 계단에서 또 1칸을 뛸 경우 3칸을 연속으로 밟게 된다.
- 한 칸 뛴 경우 = 0, 두 칸 뛴 경우 = 1로 매개변수를 넘겨 준다.
- 1칸 뛴 경우와 2칸 뛴 경우를 구분하여 계산
- 마지막 경우를 제외하고는 최댓값을 구하는 것은 의미가 없다.
- 따라서, 모든 경우를 봐야하기 때문에 각 계단마다 한 칸을 뛰고 밟은 경우와 두 칸을 뛰고 밟은 경우를 나눠서 계산한다.
- 위를 구분하지 않을 경우 다른 경로에서 밟은 최댓값이 영향을 미치게 되어 오답이 출력된다.
최종 풀이
- 마지막 계단부터 한 칸을 뛰는 경우, 두 칸을 뛰는 경우로 나눠서 하향식으로 내려간다.
소스 코드
import java.lang.Integer.max
lateinit var stairs:Array<Int>
lateinit var dp:Array<Array<Int>>
fun solve(prev:Int, now:Int, prevStairs:Int){
if(now < 0) return
if(prev + stairs[now] < dp[prevStairs][now]) return
dp[prevStairs][now] = prev + stairs[now]
if(prevStairs != 0) solve(dp[prevStairs][now], now-1, 0)
solve(dp[prevStairs][now], now-2, 1)
}
fun main(){
val n = readln().toInt()
stairs = Array(n){0}
dp = Array(n){ Array(n){0} }
repeat(n){ stairs[it] = readln().toInt() }
if(n == 1) {
println(stairs.last())
return
}
solve(0, n-1, 1)
dp[1][n-1] = stairs[n-1]
val max1 = max(dp[0][0], dp[0][1])
val max2 = max(dp[1][0], dp[1][1])
println(max(max1,max2))
}
반례
해당 문제에서 테스트했던 반례들이다.
더보기
6
100
40
10
60
70
20
답 : 220
5
50
40
30
20
10
답 : 120
1
10
답 : 10
10
100
100
1
1
100
100
1
1000
1000
1000
답 : 2302
3
40
50
60
답 : 110
3
30
20
10
답 : 40
3
10
5
답 : 20
'BOJ' 카테고리의 다른 글
[ 백준 1005 ] - ACM Craft (Kotlin) (0) | 2023.06.13 |
---|---|
[ 백준 2473 ] - 세 용액 (Kotlin) (0) | 2023.06.13 |
[ 백준 10812 ] - 바구니 순서 바꾸기 (Kotlin) (0) | 2023.03.08 |
[ 백준 1967 ] - 트리의 지름 (Kotlin) (0) | 2023.02.27 |
[ 백준 9466 ] - 텀 프로젝트 (Kotlin) (0) | 2023.02.22 |