코딩테스트 - 패스트캠퍼스 챌린지 38일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 동적 프로그래밍 (Dynamic Programming) - 2

학습 후기
동적 프로그래밍: 작은 문제로 큰 문제의 해를 구하는 방법
이번 강의에서는 이전 강의에서 동적 프로그래밍 푸는 과정에서 잘못했을 때 어떻게 다시 식을 세워야 하는지 알려주는 강의였다.

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

문제 조건
계단의 수 1 <= N <= 300
계단에 주어진 점수 1 <= score <= 10,000
출력 최대치를 확인해보면 문제 조건에서 연속된 3개의 계단을 밟을 수 없다는 조건에 의해 계단을 모두 밟을 수 없지만 다 밟는다고 했을 때, 계단의 개수 * 점수 최대치를 하면 300만으로 integer범위 안에서 해결이 가능하다.

문제 접근
처음 문제는 완전 탐색 접근 방법을 통해서 직접 하나하나씩 찾아본다.
1. 풀고 싶은 가짜 문제 정의
가짜 문제: i번째 계단에 도착하며 얻는 최대 점수
2. 가짜 문제를 풀면 진짜 문제를 풀 수 있는가?
i번째 계단에 도착하며 얻는 최대 점수의 배열을 다 구하면 N번째, 진짜 문제의 해를 찾을 수 있다.
3. 초기값은 어떻게 되는가?
0번째 계단은 오르기 전이므로 0점으로 시작한다.
4. 점화식 구하기
공통점 묶기: 마지막에 계단을 오른 수로 Partitioning 한다. 마지막에 1칸 오른 경우와 마지막에 2칸 오른 경우
묶은 부분의 정답을 배열을 통해서 빠르게 계산한다.

하지만 이렇게 해서 해를 구하면 틀린 해가 나온다. 이유는 마지막에 1칸 오른 경우 이전에도 1칸 오른 게 된다면 연속 세 칸을 오르게 되므로 조건에 맞지 않지만 따로 고려하지 않았기 때문에 해를 구하는 과정에서 포함된다. 그렇기에 1칸 전에 오른 경우를 선택했으면 그 전 경우는 2칸 전에서 오른 경우를 선택한다는 조건을 만족시켜줘야 한다.

새롭게 가짜 문제를 정의하면
1) i-1번째 계단은 밟지 않고, i번째 계단에 도착하여 얻는 최대 점수와
2) i-1번째 계단을 밟고, i번째 계단에 도착하여 얻는 최대 점수를 구해본다.
위 가짜 문제를 풀면 진짜 문제는 1), 2)의 마지막 해에서 max값을 구하면 진짜 문제의 해를 구할 수 있다.
초기값은 i = 0, 0번째는 0
1번째 i = 1,
1) 0번째 계단은 밟지 않고, 1번째 계단에 도착하여 얻는 최대 점수 10
2) 0번째 계단을 밟고, 1번째 계단에 도착하여 얻는 최대 점수 10
2번째의 i = 2
1) 1번째 계단은 밟지 않고, 2번째 계단에 도착하여 얻는 최대 점수 20
2) 1번째 계단을 밟고, 2번째 계단에 도착하여 얻는 최대 점수 30
위의 초기값으로 점화식을 계산하면
1)의 경우 i-2, i-3 두 계단을 모두 밟는 경우와, i-2는 밟고 i-3은 밟지 않는 경우를 구하여 그중 최댓값을 구한다.
2)의 경우 i-1에 오는 경우는 연속된 3 계단을 밟을 수 없으므로 무조건 i-3에서만 오는 해를 구한다.

이렇게 하면 처음 동적 프로그래밍에서 부족했던 연속한 3 계단은 밟을 수 없다는 조건도 만족시키므로 정확한 해를 구할 수 있게 된다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.