https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩
www.acmicpc.net
다이나믹 프로그래밍을 이용하였습니다.
조건3개를 잘 파악한 후 고민을 좀 했는데
2번째 문제 조건을 잘 이용해야 했습니다.
목표계단을 무조건 밟아야 한다는 가정하에(조건3)
두가지 경우의 수가 나옵니다 (조건1)
1) 바로 전계단을 밟고 목표계단을 밟는경우
2) 전전계단을 밟고 목표계단을 밟는 경우
하지만 1번 조건을 그대로 적용할 경우 3번연속된 계단을 밟게 되는 경우가 생길수 있습니다.(즉 조건2 를 무시한 상태)
즉 전계단을 밟기전에는 전전전계단을 밟았어야 한다는 조건이 들어가야 합니다.(조건추가)
dp는 최대값을 저장한 배열이고 stairvalue는 각 계단의 값을 넣어놓은 배열 입니다.
<필기>
<코드>
'알고리즘 문제풀이 > 다이나믹 프로그래밍' 카테고리의 다른 글
| 백준 11726 [C++] (0) | 2020.12.14 |
|---|---|
| 백준 7570 [C++] (0) | 2020.12.02 |
| 백준 12865 [C++] (0) | 2020.11.29 |
| 백준 1932 (0) | 2020.03.02 |
| 백준 9095 (0) | 2020.02.01 |