백준 2579번 계단 오르기 문제 풀이를 진행하였습니다.
문제 해석
문제를 읽으면 아래와 같은 해석이 가능합니다.
계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.
각 계단에는 일정한 점수가 쓰여 있으며, 밟을 때마다 그 계단에 쓰여 있는 점수를 얻게 된다.
계단을 오를 때에는 다음과 같은 규칙이 있다.
1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.
이 게임에서 얻을 수 있는 점수의 최댓값을 구해야합니다.
계단의 갯수는 최대 300개이고 계단에 적힌 점수는 10000이하의 자연수이다.
문제 풀이
계단을 오르는 모든 경우의 수를 체크함과 동시에 각 계단의 위치에서 얻을 수 있는 점수의 최댓값을 배열에 저장하며 진행해줍니다.
모든 경우의 수를 확인한 후, 마지막 계단에 있는 점수의 최댓값이 게임에서 얻을 수 있는 점수의 최댓값이 됩니다.
이때 주의할 점은 제한시간이 1초라 타임아웃이 걸릴 수 있습니다.
계단을 오를 때는 한번에 두 계단을 오를 수 있는 경우와, 전에 계단을 한칸 올라서 두 계단밖에 오르지 못하는 경우가 존재합니다.
이를 2차원 배열로 나누어 경우의 수에서 최댓값을 저장해줍니다.
예를 들면 2차원 배열의 0번째 줄에는 한번에 두 계단을 오를 수 있는 경우일 때의 최댓값을 저장해주고 1번째 줄에는 전에 계단을 한칸 올라서 두 계단밖에 오르지 못하는 경우일 때의 최댓값을 저장해줄 수 있습니다.
위와 같이 모든 경우의 수를 보며 최댓값을 저장해준다면, 후에 계산한 값이 저장된 최댓값보다 작을 경우, 이후의 계산은 필요가 없기 때문에 답을 구하는 시간이 확연히 줄어들게 됩니다.
이런 식으로 계산을 끝낸 후, 마지막 계단의 값들 중 제일 큰 값을 출력해주면 됩니다.
전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<vector<int>> dp(2, vector<int>(300, 0));
vector<int> stairs(300, 0);
void solve(int currentScore, int height, int continueStep)
{
if (continueStep >= 2 || height > n - 1)
return;
currentScore += stairs[height];
if (dp[continueStep][height] < currentScore)
dp[continueStep][height] = currentScore;
else
return;
solve(currentScore, height + 1, continueStep + 1);
solve(currentScore, height + 2, 0);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> stairs[i];
}
solve(0, 0, 0);
solve(0, 1, 0);
if(dp[0][n-1] > dp[1][n - 1])
cout << dp[0][n - 1];
else
cout << dp[1][n - 1];
}출저
