백준 2579 S3 계단 오르기

문제: 계단 오르기

접근

완전 탐색으로 접근

완전 탐색으로 접근하는 경우, 매 계단마다 한 칸과 두 칸을 어떻게 배열하여 도달할지에 관해 계산해야 하고, 그 와중에 연속된 세 칸 밟는 경우를 빼 주어야 한다.

이러면 문제가 너무 복잡해지고 시간 복잡도도 올라간다.

동적 계획법으로 접근

동적 계획법을 사용하면 문제가 정말 간단해진다.

다음을 만족하는 scores를 생각해 내는 것이 문제 풀이의 관건이라고 볼 수 있겠다.

i번째 계단에 도달했을 때, 얻을 수 있는 점수의 최대 값을 scores[i]라고 한다.

i번째 계단에 적혀 있는 점수를 steps[i]라고 할 때,

첫 번째 계단의 경우, 그냥 첫 번째 계단을 밟는 경우의 수 밖에 없으므로, score[0] = steps[0]이다.

두 번째 계단의 경우 다음의 두 가지 경우의 수 중에서 최대값일 것이다.

최종적으로 두 번째 계단을 밟았을 때 점수의 최대값은 scores[1] = max(scores[0] + steps[1], steps[1])이다.

세 번째 계단의 경우, 도 다음 두 가지 경우 수 중에서 최대값일 것이다.

최종적으로 세 번째 계단을 밟았을 때 점수의 최대값은 scores[2] = max(scores[0] + steps[2], scores[1] + steps[2])이다.

네 번째 계단의 경우,

최종적으로 네 번째 계단을 밟았을 때 점수의 최대값은 scores[3] = max(scores[3 - 3] + steps[3 - 1] + steps[3], scores[3 - 2] + steps[3]) 이다.

이를 일반화 해보면,

i를 3 이상이라고 할 때, (4번째 계단 이후) i번째 계단을 밟았을 때

따라서 i번째 계단을 밟았을 때의 점수의 최대값 scores[i] = max(scores[i - 3] + steps[i - 1] + steps[i], scores[i - 2] + steps[i])이다.

이를 도식으로 표현하면 아래와 같다.

동적 계획법을 이용하는 경우 계단 수를 N이라 했을 때, N을 한 번만 순회하면 해를 구할 수 있으므로, 주어진 제한시간 1초에 넉넉히 문제를 해결할 수 있게 된다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_STEPS 300

int N;
int steps[MAX_STEPS];
int scores[MAX_STEPS];

int main() {
  cin >> N;
  for (int i = 0; i < N; ++i) {
    cin >> steps[i]; // [1, 10^4]
  }

  scores[0] = steps[0];

  if (N < 1) goto print;

  scores[1] = max(steps[0] + steps[1], steps[1]);

  if (N < 2) goto print;

  scores[2] = max(steps[0] + steps[2], steps[1] + steps[2]);

  for (int i = 3; i < N; ++i) {
    scores[i] = max(
      scores[i - 3] + steps[i - 1] + steps[i],
      scores[i - 2] + steps[i]
    );
  }

print:
  cout << scores[N - 1];
}

← 글 목록