백준 2579 풀이

링크텍스트

풀긴 어제 풀었지만 시간이 늦어 오늘 올린다.

예전에 알고리즘 스터디를 할 때 한 번 풀었던 문제였는데 다시보니 기억이 안나 복습의 중요성을 느끼는 문제였다.

이 문제는 dp로 푸는 거다.

라는 기억 하나를 의존해서 풀었다.

처음 문제를 풀때는 시작점부터 마지막 계단까지 올라가는 과정을 코드로 작성했는데 당연히 틀렸다. 예외가 너무 많았다.

항상 거쳐가는 단계인 다른 방식으로 생각하기를 했다. 그랬더니 답이 보였다.
3번 조건에서 마지막 계단은 반드시 밟아야 하기 때문에 마지막 계단에 도착했다는 가정을 하고 1,2번 조건을 생각해서 점화식을 나타내면 된다.

따라서

score[i] = score[i-2]+stair[i] //2계단을 올라 마지막에 도착했을 때
score[i] = score[i-3]+stair[i]+stair[i-1]//연속되게 3계단을 오를 수 없기 때문에 두 계단 전에서 한 계단씩 올라온 경우

이 2경우로 나눌 수 있고 둘 중 큰 값을 선택하면 된다.

처음에 기억이 안나 조금 헤맸다... 복습하자...

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;
int dp[1000001];
int* stair;
int score[301];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int answer = 0;
	int n;
	cin >> n;
	stair = new int[n + 1];
	stair[0] = 0;
	bool isStep = false;

	for (int i = 1; i <= n; i++) {
		cin >> stair[i];
	}
	score[0] = 0;
	score[1] = stair[1];
	score[2] = max(stair[2], score[1] + stair[2]);
	for (int i = 3; i <= n; i++) {
		score[i] = max(score[i - 2] + stair[i], score[i - 3] + stair[i] + stair[i - 1]);
	}
	
	cout << score[n] << endl;

	return 0;
}