[백준/C++] 2228 - 구간 나누기

풀이 시간: 01:59:18

시간 복잡도: O(nm) → 총 n * m개의 (n, m) 쌍을 계산

공간 복잡도: O(nm) → 2차원 배열

참고

https://kmiiiaa.tistory.com/20

https://sdy-study.tistory.com/210

문제

N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.

1. 각 구간은 한 개 이상의 연속된 수들로 이루어진다.
2. 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다.
3. 정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다.

N개의 수들이 주어졌을 때, 답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 배열을 이루는 수들이 차례로 주어진다. 배열을 이루는 수들은 -32768 이상 32767 이하의 정수이다.

출력

첫째 줄에 구간에 속한 수들의 총 합의 최댓값을 출력한다.

문제 풀이

먼저 본 문제에는 정수 두 개가 주어진다.

n개의 수로 이루어진 1차원 배열 하나가 있고, 이를 m개의 구간으로 나누어 구간에 속한 수들의 총합의 최댓값을 구해야 한다.

이때, 난 앞선 2개의 dp 문제를 풀어본 경험을 토대로 2차원 배열이 하나 더 필요하다는 것을 생각했다.

그리고 그 2차원 배열은 구간별로 나누었을 때 구간에 속한 수들의 총합의 최댓값을 저장하는 공간으로 사용해야 한다는 것도 이해했다.

 

그래서 나는 다음과 같이 두 개의 정수와, 두 개의 벡터를 선언했다.

int n, m;
vector<int> arr(n + 1, 0);
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

 

처음에는 위와 같이 정수와 벡터를 선언했었는데, 나중에 코드를 구현하면서 다음과 같은 오류가 발생해서 확인해보니 잘못된 메모리 접근이 발생했다고 떴다. 다른 솔루션을 확인해보니, 선언을 먼저하고 메모리 할당을 나중에 n, m 값을 입력 받은 후 할당해주어야 한다는 것을 알았다.

 

Exception has occurred: Exception
EXC_BAD_ACCESS (code=1, address=0xa)

 

따라서 선언 부분을 다음과 같이 수정해주었다.

int n, m;
vector<int> arr; // 크기가 n인 1차원 벡터
vector<vector<int>> dp; // 크기가 n * m 2차원 벡터
...

int main(void) {
    ...
    cin >> n >> m;
    
    // 메모리 재할당, 각 벡터 초기화
    arr.resize(n + 1, 0);
    dp.resize(n + 1, vector<int>(m + 1, -1));
    ...
}

 

그런 다음에는 이제 arr 배열에 담을 숫자들을 n번 만큼 받아주어야 하기 때문에 다음과 같은 코드를 작성했다.

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

n의 범위는 1부터 n까지이므로 위와 같이 범위를 설정하여 값을 입력해주었다.

 

이후 문제에서 가장 중요한 구간에 속한 수들의 총합을 구하고 그 값들 중 최댓값을 찾는 과정에 대한 문제 접근법을 곰곰이 생각해보았지만, 도무지 떠오르지 않았다.

 

그래서 다른 솔루션을 참고하여 문제를 풀어보았다.

 

나는 dp의 top-down 방식을 이용하여 푼 솔루션을 참고하였고, 이는 재귀 방식을 사용하기 때문에 solve라는 함수를 새로 선언하여 main 함수에서 n, m 값을 인자로 받아왔다.

 

먼저 예외 처리를 if 문을 통해 3번 해주었다.

 

■ if (m == 0) return 0;

이 코드는 m이 0일 경우 0을 반환하는 것인데, 구간을 0개로 나누는 것이기 때문에 애초에 구간을 나누지 않으면 구간의 최댓값을 구할 수 없다. 따라서 0을 반환해준다.

 

■ if (n <= 0) return -1e9;

이 경우에는 앞선 문제에서 n의 범위가 1 <= n <= 100 이라고 했으므로 0보다 같거나 작을 경우에 무한대의 음수를 출력하여 에러 처리하도록 한 것이다.

 

■ if (dp[n][m] != -1) return dp[n][m];

이 부분의 경우에는 dp의 핵심 개념인 메모이제이션(memoization)을 구현한 부분이다.

메모이제이션은 이미 계산된 결과를 재활용하여 중복 계산을 방지하고 프로그램 효율성을 높이는 기법이다.

 

예를 들어, 다음과 같이 맨 처음에 dp에 있는 모든 값을 초기화할 때 -1로 초기화를 하였는데,

dp.resize(n + 1, vector<int>(m + 1, -1));

이를 이용하여 dp[n][m]이 -1이 아니라는 것은 n개의 수 중 m개의 구간을 선택하였을 때 합의 최댓값이 이미 계산되어 dp[n][m]에 저장되어 있다는 것을 말한다. 따라서 이 경우에는 이미 계산된 결과를 재활용할 수 있고 추가로 계산하지 않아도 된다.

 

그리고 난 후 구간에 속한 수의 총합을 계산하고 최댓값을 저장하는 코드를 구현하였다.

   int sum = 0, tmp = 0;
   dp[n][m] = solve(n - 1, m); // 재귀 함수, top-down 방식

   for (int i = n; i > 0; i--) { // n ~ 1 번째 수까지 반복
      sum += arr[i]; // 현재 수부터 마지막 수까지의 합(현재 구간의 합)
      tmp = solve(i - 2, m - 1) + sum; // i - 2: 다음 구간 선택 방지(최소), m - 1: 현재 구간 제외, 현재 구간의 합을 더함
      dp[n][m] = max(dp[n][m], tmp); // 더 큰 값 저장
   }

 

먼저 총합을 저장할 변수 sum과 중간에 값을 계산하기 위해 필요한 tmp 변수를 선언해주었다.

int sum = 0, tmp = 0;

 

그리고 처음에는 재귀 함수를 사용하여, 'n-1'개의 수 중 'm' 개의 구간을 선택했을 때의 최대 합을 구해준다. 즉, 'n'개의 수 중 마지막 수를 선택하지 않고 'm'개의 구간을 선택했을 때의 최대 합을 dp[n][m]에 저장해주는 것이다.

dp[n][m] = solve(n - 1, m);

 

그리고 난 후 for문을 통해 마지막 n번째 수부터 1번째 수까지 차례대로 반복하면서 그 구간의 합을 구해준다.

for (int i = n; i > 0; i—) {

      sum += arr[i];

      ....

 

이때 tmp에는 'i - 2'개의 수 중에서 'm - 1'개의 구간을 선택했을 때의 최대 합(solve(i - 2, m - 1))과 현재 구간의 합(sum)을 더해준다. 여기서 'i - 2'인 이유는 구간들이 서로 겹치지 않게 하기 위함이다.

tmp = solve(i - 2, m - 1) + sum;

 

예를 들어, 배열이 [10, 20, 30, 40, 50]이라고 가정하자.

이때 인덱스는 1부터 시작한다고 치자. 그렇게 되면 30의 인덱스는 3, 40의 인덱스는 4 이런식으로 위치하게 된다.

만약 i가 40이라면, 구간은 최소한 하나 이상의 연속된 수로 이루어져야 하기 때문에 최소한 {40}부터 가능하다. 또한 문제의 또 다른 조건에서는 두 개의 구간이 서로 겹치거나 인접해 있어서는 안된다고 했기 때문에, 만약 'i - 1'이 될 경우, 인덱스 3에 해당하는 30의 값에 해당하므로, 30은 40과 인접해있기 때문에 'i - 1'부터 구간을 시작할 수 없다. 따라서 최소한 'i - 2'를 사용해야 한다.

 

마지막으로 dp[n][m]에 현재 dp[n][m]의 값과 tmp 값 중 더 큰 값을 저장해준다.

dp[n][m] = max(dp[n][m], tmp);

 

계산이 모두 끝나면 dp[n][m] 값을 출력하면 된다.

return dp[n][m];

전체 코드

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> arr; // 크기가 n인 1차원 벡터
vector<vector<int>> dp; // 크기가 n * m 2차원 벡터

int solve(int n, int m) {
   if (m == 0) return 0; // 구간
   if (n <= 0) return -1e9; // n의 범위는 1 <= n <= 100이므로 0보다 같거나 작을 경우 에러
   if (dp[n][m] != -1) return dp[n][m]; // 메모이제이션(memoization)

   int sum = 0, tmp = 0;
   dp[n][m] = solve(n - 1, m); // 재귀 함수, top-down 방식

   for (int i = n; i > 0; i--) { // n ~ 1 번째 수까지 반복
      sum += arr[i]; // 현재 수부터 마지막 수까지의 합(현재 구간의 합)
      tmp = solve(i - 2, m - 1) + sum; // i - 2: 다음 구간 선택 방지(최소), m - 1: 현재 구간 제외, 현재 구간의 합을 더함
      dp[n][m] = max(dp[n][m], tmp); // 더 큰 값 저장
   }

   return dp[n][m]; // 크기가 n인 배열을 m개의 구간으로 나누었을 때 구간에 속한 수들의 총합의 최댓값
}

int main(void)
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   cin >> n >> m;

   // 메모리 재할당, 각 벡터 초기화
   arr.resize(n + 1, 0);
   dp.resize(n + 1, vector<int>(m + 1, -1));
   
   for (int i = 1; i <= n; i++) cin >> arr[i];

   cout << solve(n, m) << "\n";
}

 

궁금한 점

분명 본 문제는 n개로 이루어진 1차원 배열을 이루는 수들이 -32768 이상 32767 이하의 정수라고 명시되어 있는데, 대부분의 솔루션들이 해당 값의 범위를 갖는 short, short int, signed short int를 사용하지 않고 그냥 int로 선언한 이유가 뭘까?

 

이를 뤼튼의 gpt-4께 여쭤보았다..

답변은 다음과 같았다.

 

"arr 벡터에는 입력으로 받는 각각의 원소들이 저장되므로, 각 원소는 -32768 이상 32767 이하의 정수 범위에 속하게 됩니다. 따라서 이론적으로 arr 벡터의 데이터 타입을 signed short int로 설정해도 문제는 없습니다.
그러나, 실제로 int와 signed short int 사이에 메모리 사용량의 차이는 크지 않으며, 대부분의 컴퓨팅 시스템에서 int의 처리 속도가 더 빠르기 때문에, 일반적으로는 int를 사용하는 것이 더 효율적입니다. 또한, 코드의 일관성을 유지하고 가독성을 높이기 위해 arr 벡터의 데이터 타입도 int로 설정하는 것이 좋습니다."

 

그렇다고 한다.

 

https://www.acmicpc.net/problem/2228

2228번: 구간 나누기