7주차 - 동적계획법 (백준 2579번)

동적계획법(Dynamic Programming)

: 복잡한 문제를 간단한 여러 개의 문제로 나누어 접근하는 방법이다.

부분 문제가 반복되고 최적의 원칙을 만족하는 문제를 일반적인 방법에 비해 적은 시간 내에 풀 때 사용한다.
ex) 피보나치, 정수삼각형, 이항 계수

• 상향식 해결법(Bottom-Up 방식)
  아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식
• 최적의 원칙
  : 어떤 문제의 입력에 대한 최적해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 적용된다고 한다.

---

백준 2579번: 계단 오르기

#include<iostream>
#define MAX 301
using namespace std;

int main() {
	int n;
	int DP[301];  // 계단까지의 최댓값
	int score[301] = {0, };  // 계단의 점수
	
    cin >> n;
    int i;
    for(i = 1; i <= n; i++)
        cin >> score[i];
	
    DP[1] = score[1];  // 1번째 계단까지의 최대값 
    DP[2] = score[1] + score[2];  // 2번째 계단까지의 최대값  
    DP[3] = max(score[1], score[2])+score[3];   // 3번째 계단까지의 최대값 
	
    for(i = 4; i <= n; i++)
        DP[i] = max(DP[i-3] + score[i-1], DP[i-2]) + score[i];
    
    cout << max(DP[n-1], DP[n]) << '\n';
}

각 계단의 점수를 저장하는 배열 score[] (이때 score[0]=0으로.. 사용하지 않는다.)와
계단까지의 최댓값을 저장하는 배열 DP를 설정한다.

예제 입력을 입력했을 때 맞는 결과가 나왔는데.. 백준에서는 틀렸다고 나왔다.

백준에서는 틀렸다고 나왔다!

따라서 코드를 다시 수정했다.

3번째 계단까지의 최대값을 생각해보면, "1번 계단+3번 계단인 경우" 또는 "2번 계단 + 3번 계단인 경우" 2가지 중 큰 값이므로 코드를 아래와 같이 변경하였다.

DP[3] = max(score[1]+score[3], score[2]+score[3]);

 

 

이를 확장하면 i번째 계단까지의 최대값은 아래와 같다.

DP[i] = max(DP[i-2] + score[i], DP[i-3] + score[i-1] + score[i]);

 

최종 코드는 아래와 같다.

#include<iostream>
#define MAX 301
using namespace std;

int main() {
	int n;
	int DP[301];  // 계단까지의 최댓값
	int score[301] = {0, };  // 계단의 점수
	
    cin >> n;
    int i;
    for(i = 1; i <= n; i++)
        cin >> score[i];
	
    DP[1] = score[1];  // 1번째 계단까지의 최대값 
    DP[2] = score[1] + score[2];  // 2번째 계단까지의 최대값  
    DP[3] = max(score[1]+score[3], score[2]+score[3]);   // 3번째 계단까지의 최대값 
	
    for(i = 4; i <= n; i++)
        DP[i] = max(DP[i-2] + score[i], DP[i-3] + score[i-1] + score[i]);
    
    cout << DP[n] << '\n';
}

이번엔 정답이다!!