[백준(BOJ)] 10211번 Maximum Subarray C++

문제 : https://www.acmicpc.net/problem/10211

10211번: Maximum Subarray

 

 

 

어떤 문제인가?

크기가 n인 정수 배열의 부분 배열 중 각 원소들의 합이 가장 큰 부분 배열을 찾아 그 합을 출력하는 문제이다.

 

 

접근 방법

일단 이 문제는 dp의 방식으로 접근했다.

코드를 보자.

 

int t;
cin >> t;

테스트 케이스의 수를 입력받는다.

 

while (t--) {
    int n;
    cin >> n;

    int arr[n + 1];
    int dp[n + 1];
    dp[0] = 0;
    int maxNum = INT_MIN;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    for (int i = 1; i <= n; i++) {
        dp[i] = max(arr[i] + dp[i - 1], arr[i]);
        maxNum = max(maxNum, dp[i]);
    }

    cout << maxNum << "\n";
}

정수 배열을 저장할 arr과 dp값을 저장할 dp배열을 선언해준다. 이 둘의 크기는 n+1로 해준다. 

 

n번만큼 정수 배열의 값들을 입력받는다.

 

이제 반복문을 통해 dp값을 계산해 볼 것이다.

 

문제의 예시로 살펴보자.

 

2 1 -2 3 -5가 입력됐다.

 

당연히 dp [ 1 ] =2가 된다.

dp [ 2 ] = 3이 되는 것도 당연하다.

 

dp [ i ] = x의 뜻은 i번째까지 부분 배열의 최댓값은 x다 라는 뜻이다.

 

dp [ 3 ]은 dp[ 2 ]와 dp[ 2 ] + (-2) 둘 중의 큰 값이 될 것이다.

왜냐하면 그다음 값을 더 했을 때 이전 보다 값이 더 작아지면 그 다음 값을 더할 이유가 없다.

그리고 또 dp [ i ]의 값과 비교를 위한 maxNum를 비교해 둘 중 더 큰 값을 maxNum으로 바꿔준다.

 

그리고 반복이 끝났을 때 maxNum을 출력해준다.

 

 

무엇이 어려웠는가?

 

dp[i] = max(arr[i] + dp[i - 1], arr[i]);

처음엔 이 식만 쓰면 dp[ n ]에 최댓값이 저장되어있을 거라고 생각했다.

하지만,생각해보니 dp [ n ] 값은 부분배열이 아니라 그냥 배열 전체의 합이었다.

 

그래서 부분배열의 합을 비교할 값이 필요했고 maxNum을 INT_MIN으로 초기화해주어 비교를 해줬다.

 

 

배운 점

머리로는 당연하게 여겨져 생각도 안하는 부분을 코드로 구현하는 실력을 더 키워야겠다.