BOJ 2579 계단 오르기

문제출처 : https://www.acmicpc.net/problem/2579

1. 문제요약

- 계단을 하나 건너 뛸 수 있음

- 최대 2번 연속으로만 밟을 수 있음

- 마지막 계단은 무조건 밟아야 함

- 1, 2, 4, 5 순으로 밟는건 가능

- 1, 2, 3, 4 순으로 밟는건 불가능 / 1, 2, 3 이 연속으로 3번 밟았기 때문

- 최대 합은?

2. 접근방법

- 방법 1.

  d[n] : n번째 계단에서 최대합

  현재 계단을 밟는 경우는 전전 계단을 밟고 한칸 뛰어서 현재 계단을 밟는 경우

                                  전 계단을 밟고 바로 연속으로 현재 계단을 밟는 경우

  하지만 전계단을 밟고 현재 계단을 밟는다면 현재를 n이라 했을 때, n-1번째 계단을 밟고 온 경우가

  n-1에서 두번 연속으로 밟은 경우인지 알 수 없음.

  그래서 n-3에서 최대합에서 n-2를 건너뛰고 n-1과 n 값을 합하면 됨

  d[n] = max(d[n-2] , d[n-3] + a[n-2]) + a[n]

- 방법 2.

  포도주 시식과 비슷한 방법으로

  d[3] : d[0] - 현재 계단을 밟지 않았을 때 최대합

          d[1] - 현재 계단이 연속 1회 일때 최대합

          d[2] - 현재 계단이 연속 2회 일때 최대합

  d[0] = max(d[1], d[2])

  d[1] = d[0] + a

  d[2] = d[1] + a

3. 시간복잡도

- 방법 1, 2 모두 n

4. 회고

- 포도주 시식 boj 2156 과 같은 문제

소스코드 방법 2

#include<iostream>
using namespace std;

int n, a, temp, d[3];

int max(int a, int b){
	return ((a < b) ? b : a);
}
int main(void){
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a;
		temp = max(d[1], d[2]);
		d[2] = d[1] + a;
		d[1] = d[0] + a;
		d[0] = temp;
	}
	cout << max(d[1], d[2]) << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]