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

연속합을 구하는 문제.

 

경우의 수를 잘 생각해내야 하는게 동적계획법 문제 풀이에 있어서 중요한 시작점인 것 같다.

말하자면 점화식을 세우는 것..

 

처음에는 다소 단순하게 문제에 접근했다.

 

마이너스가 껴있으면 당연히 연속합이 최대가 되지 못할 것이라고 생각해서, 그냥 수를 입력받다가 마이너스를 만나면 새출발하는 느낌으로 코드를 구성했다. (동적계획법느낌의 코드는 아니였다)

 

그러다가 테스트케이스에서 반례를 발견했다.

10
2 1 -4 3 4 -4 6 5 -5 1

마이너스가 껴있더라도 연속합이 최대가 될 수도 있다는 것.

 

 

그래서 다시 처음부터 시작했다.

 

우선 경우의 수를 4가지로 나열했고, 이걸 다시 두가지로 추릴 수 있었다.

 

 1. 이전까지의 최대합에서 지금껄 선택한다.

 2. 이전까지의 최대합에서 지금껄 선택안한다. -> 연속되어야 하므로 제외

 3. 지금껄 처음으로 선택한다.

 4. 지금껄 처음으로 선택안한다. -> 연속되어야 하므로 제외

 

 

이를 기반으로 구성해본 식은 아래와 같다.

// arr[i] 는 i번째까지의 연속합 최대값.
 
 arr[i] = arr[i] > arr[i - 1] + arr[i] ? arr[i] : arr[i - 1] + arr[i];
 
// + 등호(=)위치는 상관없으므로 아무데나 넣어줄 예정.

 

이를 코드로 작성했다.

// 이 문제는 포도주문제와 비슷하게, 꼭 마지막 인덱스값을 결과로 참조할 필요가 없다 = 선택안하는 경우도 마지막인덱스로 이어져야 한다 -> 계단문제와 달랐던 차이점이다. 하지만 포도주문제와 다른점은 '연속' 이 기반이 되어야 하기 때문에, 선택안하는 경우에 대한 값을 다음에 쓸 수가 없다.
// 두 가지 방법이 있다. 위에서 말한 '선택 안하는 경우'를 넣어주는 방법(=선택하지않고도 현재까지의 기존의 최댓값을 저장. 하지만 이 값을 이후에 사용할 순 없음... 이게 최대 어려운 점), 그리고 포문 안에서 if문으로 최댓값을 선정해내는 방법(이건 간단하다. MAX값의 초깃값 설정만 잘 하면)

#include <stdio.h>

int arr[100001]; // N의 최대크기는 100,000 이지만, 0번째를 0으로 두고 1번째 인덱스부터 값을 입력받아 연산 과정을 통일화시킬수있게 구성.

int main() {

    int N;
    int MAX = -100000000; // 각 자리수는 최솟값이 -1000 이며, 최대 N은 100,000이니까 둘을 곱한다.
    scanf("%d", &N);
    
    
    for(int i = 1; i <= N; i++) {
        
        scanf("%d", &arr[i]);
        
        arr[i] = (arr[i] >= arr[i - 1] + arr[i])? arr[i] : arr[i - 1] + arr[i];
        
        if(MAX <= arr[i])
            MAX = arr[i];
        
    }
    
    printf("%d", MAX);
}

 

점화식 구성이 동적계획법 문제의 전부.

 

 

 

이 문제에 겁먹어서 1달정도 이 문제풀기를 미뤘었는데, 잘 마무리 할 수 있었다.

AI 부스트캠프 3차 코딩테스트에서 갑자기 머리가 하얘져서 정말 아무생각도 안나서 문제를 풀어나가지도 못했고, 정말 자존감이 많이 떨어졌었는데 내 자존감을 다시 쌓아나가는데 시작점이 되어준 문제였다. 힘들면 이 문제보러 다시 와야지.

 

 

---

2021.02.25 복습

다시풀어보았다.

 

예전에 동적계획법에 대해 많은 혼란을 겪어서 이 문제 푸는 것을 점점 미루고 미루다 풀었었는데, 걱정과 달리 잘 풀어냈었다.

오히려 스스로 걱정하고 회피했던 것 자체가, 문제되지 않는 것을 문제로 삼아서 문제가 되었던 것 같다. 그렇게 혼란스럽다고 되뇌던 때에 풀었던 위 방식과 생각에 대한 정리가, 지금보다 더 정확하다.. 오히려 지금, 이 때의 내 생각에 대한 글을 보고 배우고 있다..

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

int N;
int MAX = -100000001;
int dp[100001];
int v[100001];

int main() {
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++) {
        scanf("%d", &v[i]);
        
        dp[i] = MAX(dp[i - 1] + v[i], v[i]);
        
        if(MAX < dp[i])
            MAX = dp[i];
    }
    
    printf("%d", MAX);
}



/*
 
 연속합
 
 A. 이전까지의 연속합 + 내 값
 
 B. 현재 내 값(시작으로 두는것)
 
 dp[i] = MAX(A, B)
 
 if MAX < dp[i]
    MAX = dp[i]
 
 정답 : MAX

 
 */

처음 풀었던 방식은 배열을 하나로만 잘 사용했는데 ㅜ 이번엔 두개 사용했다.

 

 

계단, 와인, 연속합 이런 문제를 풀면서 강박이 좀 생긴 것 같다..

이건 이런 유형이고 이건 조금 다른 유형이라, 이건 이렇게만 해야되고 이건 저렇게만 해야된다는 집착을 가질 필욘 없을 것 같다..

이런 옳고 그름을 두려고 하는게, 문제되지 않는 걸 굳이 계속 문제삼는 격이다 ㅜ