[BaekJoon/백준] 2156번 | 복습 1회 완료

이전 계단문제인 2579번과 아주 유사한 문제다. (계단 문제 응용버전이라고 볼 수 있음)

 

기존의 계단 오르기 문제는 아래와 같다.

A B C D가 있을 떄, D까지 오기 위한 방법은

1. B까지 오른 뒤 D를 오른다.

2. A까지 오른 뒤 C로 간 뒤 D를 오른다.

둘 중 최댓값을 선택
    

하지만 해당 문제는 가장 마지막 계단의 계산값을 찾는 게 아니라, 각 계단까지 오르는데의 최댓값을 계단별로 비교해서 최댓값을 얻어낸다.

ex) A B C D E가 있을 때, D까지 최대로 오르는 것이 E까지 최대로 오르는 것 보다 값이 클 수가 있다.

      1 2 9 3 2 -> D 까지 최댓값 13, E까지 최댓값 12 (기존 계단문제 기반 예시)

기존 계단문제는 이런 값을 도출하게 된다.

 

여기서 조금 응용을 해야 이 문제를 풀 수 있다.

이 문제는 '계단' 에 관한 문제가 아니라 '와인' 이지만, 이전 계단문제와의 차이점을 언급하기 위해 통일해서 '계단'이라고 말하겠다.

 

여기서, E까지의 값인 인덱스에 13이 아닌 12를 넣게 되면, E 이후의 계단이 있을 경우 계산되는 추가데이터에 문제가 생긴다. 그래서 '해당 계단을 밟지 않는 경우', 다시말해 'n - 1까지의 계단최댓값 + n계단을 밟지 않음' 의 값의 비교도 필요하다.
    

또한 해당 문제는 이전 계단문제처럼 1칸만 뛸 수 있는 게 아니라, 3개가 연속되지만 않는다면 여러 칸 뛸 수 있다.

A B C D E F

하지만 고려할 필요가 없다. F까지 온다고 C에서 바로 올 필요가 없는 것이,(n-2부터는 고려할 필요가 없는 이유) 위에서 언급했듯이 F까지 오는 자리는, 이후 뒤에 G H 등등이 있다 하더라도, 고유한 독립적인 값이므로 F까지를 기준으로 생각해서 3개까지만 안겹치면 된다. 따라서 C에서 바로 F까지 오는 것 보다 CD F 하던가 C EF 하는 값이 더 크게 된다.
    

#include <iostream>
using namespace std;
#define MAX(a, b) ((a<=b)?b:a) // 같을 경우는 이전 계단문제도 그렇고, 어느 쪽이던 상관없음. 각 인덱스의 값은 '해당 자리까지'오는데에 기여한 독립적인 고유의 값이므로. (최적 부분 구조)

int N;
int a[10003]; // 앞의 세자리는 비워두고 네자리부터 사용하기 위해.
int result[10003]; // 결과
//int ans = -1;

int main() {
    
    cin >> N;
    
    // 참고로 이전의 계단문제에서는 i = 4부터 했는데, 인덱스 한 개 낭비였다. i = 3부터 해도 앞의 세 자리 0 1 2를 비우는 데 충족된다.
    for(int i = 3; i < N + 3; i++) {
        cin >> a[i];
        result[i] = a[i];
                
                
        result[i] = MAX(MAX(result[i - 2]+a[i], result[i - 3]+a[i - 1]+a[i]), result[i - 1]);
        
        /*
        if(ans < result[i]) // 현재까지의 dp 목록의 최댓값.
            ans = result[i];
         이것도 이렇게 해줄 필요 없는 이유 => 어차피 연쇄적인 구조 기반이므로, n - 1 자리까지 시음하고 n 자리 시음 안하게 되면 n + 1도 그렇게 사용할 수 있게 되니까, 바로 이전의 n - 1까지의 시음 + n을 안하는 경우 만 넣어주면 알아서 처리된다.
         다시말해, 처음부터 아예 이전 자리까지 마시고 현재 자리를 마시지 않는 경우에 대한 비교를 거쳐왔기 때문에.
         */

    }
    
    //cout << ans;
    cout << result[N + 2];
    
}

 

아래는 주석 없이 코드만 넣은 코드다.

#include <iostream>
using namespace std;
#define MAX(a, b) ((a<=b)?b:a)

int N;
int a[10003];
int result[10003];

int main() {
    
    cin >> N;
    for(int i = 3; i < N + 3; i++) {
        cin >> a[i];
        result[i] = a[i];
        
        result[i] = MAX(MAX(result[i - 2]+a[i], result[i - 3]+a[i - 1]+a[i]), result[i - 1]);
    }
    
    cout << result[N + 2];
}

 

많은 분들의 도움을 받았다.

www.acmicpc.net/board/view/60664

('이러면 33이 저장되어야 하는데 32가 저장됐으므로 뒤에 추가 데이터가 있을 경우 계산 중 문제가 발생할 수 있는 여지가 당연히 있습니다.'  부분 주목!)  - dp[i - 1] > dp[i] 인 경우가 존재하므로 이를 생각하여 유의하라는것.

www.acmicpc.net/board/view/49900

(현재 자리를 시음하지 않는 상황에서 n - 2 부터에 대한 생각이 필요 없는 이유)

 

 

---

2021.02.24 복습

다시 풀어보았다.

#include <stdio.h>
#define MAX(a,b) ((a<=b)?b:a)

int N;
int dp[10004]; // 여분으로 앞에 3칸 비움
int w[10004]; // 여분으로 앞에 3칸 비움

int main() {
    
    scanf("%d", &N);
    
    for(int i = 3; i < N + 3; i++) {
        scanf("%d", &w[i]);
        
        // 기존 계단문제 방식에서 마시지 않는 경우도 추가. (이전까지의 최댓값을 그대로 사용)
        dp[i] = MAX(dp[i - 1], MAX(dp[i - 3] + w[i - 1] + w[i], dp[i - 2] + w[i]));
    }
    
    //dp[K] 에는 K까지 고려했을 때, 최댓값이 들어가게 됨.
    printf("%d", dp[N + 2]);
}


/*
 
 와인문제
 
 dp[N] : N번째 잔까지 고려했을때(안마시는 경우도 존재한다), 최댓값.
 해당 자리를 선택안하는 경우도 들어간다는 점에서 계단문제와 조금 다르다.
 
 
 A 마신다 (계단과 동일 유형)
 dp[i] = dp[i - 3] + w[i - 1] + w[i];
 
 dp[i] = dp[i - 2] + w[i];
 
 B 안마신다
 dp[i] = dp[i - 1];
 
 점화식은
 dp[i] = MAX(A, B)
 

 */

맨 위에서 이미 설명할 걸 보면 알 수 있듯, 와인문제와 계단문제는 유형의 차이가 존재한다.

만약 계단문제가 와인문제와 동일한 유형이였다면 정답인 dp[N]은 계단을 오르는 방법 중 최대 점수값이 되었을 것 같다.

 

추가 참고

: st-lab.tistory.com/135

: hoony-gunputer.tistory.com/entry/dp-백준-2156-포도주-시식

 

21.02.26

약간..추가로 생각나는대로 조금 정리하자면?

'N까지 고려했을때' 는, 뽑지 않는 경우도 존재한다.

주로 '뽑는 경우의 최댓값' 을 구할 때 사용할 것 같다. -> dp[N] = N까지 고려했을 때 최댓값.

 

그리고 계단같이, 'N자리까지 뽑았을 때', 는 'N까지 뽑는 경우의 최댓값'을 구할 때 사용하며, 해당 자리가 꼭 들어간 경우 중 최댓값이겠다.

 -> dp[N] = N 까지의(포함) 최댓값. 따라서 경우에 따라 N - 1 까지 뽑았을 때가 N까지 뽑았을 때 보다 클 수도 있다 (dp[N - 1] > dp[N]).

 

 

 

+ 그리고 중요하진 않지만, 메모 하나 하자면.. (안읽어도 됨)

계단문제, 와인잔문제, 연속합 문제가 비슷한 점이 있다보니

자꾸 공통점-차이점을 비교해보고 분석하여 파고들면서, 이건 이럴 때 저건 저럴 때 이런것에 대한 확실한 구분에 집착하다가 생각이 더 복잡해진 것 같다. 그냥 각각의 문제로 잡고, 구분에 대한 집착없이 풀어나가는게 편할 것 같다.

각각 다 다른점이 있는데, 비슷한 점에 대해서만 놓고 접근하는 어설픈 관점으로 문제가 더 헷갈려진다. (백준 동적계획법 질문글 & 네전따 질문글 답변) 문제 하나 하나를 각각 받아들이고, 각 상황의 유형으로 흡수하는게 나을 것 같다.