![백준 2579번 계단 오르기 [ Java ]](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FcSDmyK%2FbtqCYGyi1sE%2FAAAAAAAAAAAAAAAAAAAAAK7fBYYrMZeh7hughoOnVbSyDNVe5At4om9F-vPZNIIv%2Fimg.png%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1767193199%26allow_ip%3D%26allow_referer%3D%26signature%3DygGRG51bHzLXR1PqJtg6%252B2fQV0o%253D)
반응형
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩
www.acmicpc.net
풀이 방법이 떠오르지 않아 구글링해서 풀었습니다.
맨 마지막 계단은 꼭 밟는 경우는 연속 3번이 불가능하기 때문에 두 가지 경우가 있습니다.
1. 이전 계단과 연속해서 밟기 ( n-1밟고 n 밟기 )
2. 이전 계단과 연속하지 않고 밟기 ( n-2밟고 n 밟기 )
첫 번째 경우부터 보면 n번째 계단을 밟기 위해선 n-2번째 계단까지 계산해준것에 n번째 계단의 숫자를 더해주어야 합니다. -> dp[n-2] + stair[n]
두 번째 경우는 n-3번째 계단까지 계산해준 것에 n-1번째 계단의 숫자와 n번째 계단의 숫자를 더해주어야 합니다.
-> dp[n-3] + stair[n-1] + stair[n]
이 두 가지 경우에서 더 큰 경우를 선택해주면 됩니다.
반응형
'Algorithm' 카테고리의 다른 글
| 백준 1463번 1로 만들기 [ Java ] (0) | 2020.03.29 |
|---|---|
| 백준 10996번 별 찍기 - 21 [ Java ] (0) | 2020.03.28 |
| 백준 2446번 별 찍기 - 9 [ Java ] (0) | 2020.03.16 |
| 백준 2523번 별 찍기 - 13 [ Java ] (0) | 2020.03.16 |
| 프로그래머스 코딩테스트 연습 SQL SUM,MAX,MIN (0) | 2020.03.12 |