[BaekJoon 2579][⚪3] 계단 오르기
❓ 문제
🎯 난이도
Silver ⚪3
🧠 풀이
1. 내 풀이 (DP)
- 알고리즘
Dynamic Programming
- 설명
DP 알고리즘을 사용한 풀이이다.
원하는 상황에서의 최대의 값을 구하는 문제이고, 이는 점화식을 세워 DP 방식으로 충분히 풀 수 있는 문제이다.
어떤 i번째의 계단을 오를 때, 그 계단에 오를 수 있는 방법은 2가지 뿐이다.
i - 2 -> i식으로i - 1을 밟지 않고 가는 방법.i - 3 -> i - 1 -> i식으로 2번 연속으로 밟고 가는 방법.
문제의 조건인 연속 3개의 계단을 밟지 않고 가는 방법은 위 두 가지 뿐이다. 따라서 이를 점화식으로 나타내면 다음과 같다.
\[dp[i] = max(dp[i − 2] + stair[i], dp[i − 3] + stair[i − 1] + stair[i])\]
이 점화식을 바탕으로, 몇 개의 초기값을 가지고 코드를 만들면 끝이다.
N번째 계단의 값을 구하는 데는 N번의 반복이 필요하므로 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
vector<int> vecStair(iN + 1);
for(int i = 1; i < iN + 1; ++i)
{
cin >> vecStair[i];
}
// iN 까지의 DP 배열
vector<int> vecDP(iN + 1);
// 0, 1, 2번째 계단에서의 최대값
vecDP[0] = 0;
vecDP[1] = vecStair[1];
if(iN >= 2)
{
vecDP[2] = vecStair[1] + vecStair[2];
}
// DP 점화식에 따라 최대값 계산 및 저장
for(int i = 3; i < iN + 1; ++i)
{
vecDP[i] = max(vecDP[i - 2] + vecStair[i], vecDP[i - 3] + vecStair[i - 1] + vecStair[i]);
}
cout << vecDP[iN];
return 0;
}
2. 추가 풀이 (최적화된 DP)
- 알고리즘
Dynamic Programming
- 설명
DP 알고리즘을 사용하지만 더 최적화된 방식이다.
위의 DP 알고리즘과 동일하지만, 메모리적으로 더 최적화하는 방법이 존재한다. 이는 상기한 로직에서 지속적으로 필요한 값이 몇 개로 제한이 되어 있다는 것을 이용한 것이다.
DP[i]를 구하기 위한 값은 점화식을 보면 알 수 있듯이, DP[i - 2], DP[i - 3]만 필요하다. 따라서 N까지의 모든 값들을 저장하기 위한 배열을 만드는게 아니라, 단 세 개의 변수만을 선언하고 매 루프마다 값을 갱신해 나가는 방식으로 메모리를 확 줄일 수 있다.
위와 같이 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
vector<int> vecStair(iN + 1);
for(int i = 1; i < iN + 1; ++i)
{
cin >> vecStair[i];
}
// iN = 1, 2일 때는 바로 출력 후 종료
if(iN == 1)
{
cout << vecStair[1];
return 0;
}
else if(iN == 2)
{
cout << vecStair[1] + vecStair[2];
return 0;
}
// 0, 1, 2번째 계단에서의 최대값
int iDP1 = vecStair[1];
int iDP2 = vecStair[1] + vecStair[2];
int iDP3 = max(iDP1 + vecStair[3], vecStair[2] + vecStair[3]);
// DP 값을 계산하고 미리 선언한 변수의 값들을 차례로 갱신
for(int i = 4; i <= iN; ++i)
{
int iDP{ max(iDP2 + vecStair[i], iDP1 + vecStair[i - 1] + vecStair[i]) };
iDP1 = iDP2;
iDP2 = iDP3;
iDP3 = iDP;
}
cout << iDP3;
return 0;
}
💭 후기
같은 DP 로직을 사용하더라도, 두 번째 풀이의 메모리 사용량이 훨씬 적다. 이런 식으로 같은 로직 내에서도 여러 최적화 방법이 있으니, 풀고 나서도 꼭 더 좋은 방법이 있을지 한번쯤은 고민해보자
Comments