https://www.acmicpc.net/problem/2579
N개의 계단이 있고 계단마다 일정한 점수가 주어져있다. 시작 지점부터 마지막 계단까지 올랐을 때 얻을 수 있는 점수의 최댓값을 구하는 문제다. 계단을 오르는 규칙은 다음과 같다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
- 연속된 세 개의 계단을 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단을 반드시 밟아야 한다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ N ≤ 300
- 계단마다 쓰여 있는 점수는 10,000 이하의 자연수
점수를 저장할 배열과 각 계단까지 도달했을 때 얻을 수 있는 점수들의 최댓값을 저장할 dp 배열을 선언해야 한다. 최댓값은 300 × 10,000으로 int 범위 안에서 해결 가능하다.
DP 문제라 우선 점화식을 찾는 데에 집중했다.
예를 들어 3번째 계단까지 도달할 수 있는 방법은 다음과 같다.
- 0 → 1 → 3
- 1 → 3
- 0 → 2 → 3
4번째 계단까지 도달할 수 있는 방법은 다음과 같다.
- 0 → 1 → 3 → 4
- 1 → 3 → 4
- 1 → 2 → 4
- 0 → 2 → 4
잘 살펴보면 n번째 계단에 도달하려면 n-3번째 계단에서 n-1번째 계단을 하나 밟고 한 칸 더 밟거나, n-2번째 계단에서 계단을 2개 밟아야 한다. 이후 둘 중 더 높은 값을 dp 배열에 저장하면서 dp 배열의 n번째 값을 구해야 한다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- n 입력받기
- 첫 번째 계단과 두 번째 계단의 점수를 받아 배열에 저장하고, dp 배열에도 저장하기
- 세 번째 계단부터 반복문을 통해 점수를 입력받고, 위에서 구한 규칙을 통해 dp 배열 값을 채우기
- dp[n-1] 출력하기
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
pass
정답 코드
#include <iostream>
#include <algorithm>
using namespace std;
int n,x[301],dp[301];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
cin >> x[0] >> x[1];
dp[0] = x[0];
dp[1] = x[0] + x[1];
for (int i=2; i<n; i++) {
cin >> x[i];
dp[i] = x[i] + max(dp[i-2],dp[i-3]+x[i-1]);
}
cout << dp[n-1];
}