[BAEKJOON] 2579번 계단 오르기

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>

int main() {
	int N; 
	std::cin >> N;

	int *stairs	{ new int[N] };
	int *temp	{ new int[N] };

	for (int i = 0; i < N; ++i) std::cin >> stairs[i];

	temp[0] = stairs[0];
	temp[1] = stairs[0] + stairs[1];
	// 2stair 0 + 2, 1 + 2
	temp[2] = std::max(stairs[0] + stairs[2], stairs[1] + stairs[2]);

	for (int i = 3; i < N; ++i) {
		// i stair = compare i - 2 + i, i - 3 + i - 1
		temp[i] = std::max(temp[i - 2] + stairs[i], temp[i - 3] + stairs[i - 1] + stairs[i]);
	}
	std::cout << temp[N - 1];



	delete[] stairs;
	delete[] temp;

	return 0;
}

 

풀 이

 

• 계단 n번째를 밟을 경우 

  n - 3, n - 1, n을 밟는 경우 0 x 0 0 

  n - 2, n 을 밟는 경우        x 0 x 0

• 위의 경우 앞에 n - 3 / n - 2가 계단에 누적된 값이라면, 
  0 x 0 | x 0 x | x x 0 | 0 0 x 나올 수 있는 4가지를 모두 확인하면서 최댓값을 가져왔기 때문에 
  ( 누적된 i - 2 계단의 값 + i번 계단의 점수 ) 와 ( 누적된 i - 3 계단의 값 + i - 1 계단의 점수 + i 계단의 점수 )를
  비교하여 높은 값을 그 계단의 누적값으로 저장하면 된다.
  
  

결 과 값

 

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/2579