수 고르기( BOJ 20186 )

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

20186번: 수 고르기

 

문제 파악하기

적절하게 K개의 숫자를 선택하여 얻을 수 있는 점수의 최댓값을 구하는 문제입니다. 점수는 선택한 K개의 숫자에서 얻을 수 있으며, 현재 숫자를 기준으로 왼쪽에 있는 숫자 중 선택된 수의 개수를 현재 숫자에서 뺀 값을 의미합니다. 어떻게 하면 점수를 최대로 만들 수 있을까요? 확인하는 방법은 여러가지 있습니다.

 

문제 해결하기

가장 떠올리기 쉬운 방법은 모든 경우의 수를 찾아보는 것입니다. 문제를 함수를 사용하여 상태로 추상화하면 우리는 무식하지만 확실하게 모든 경우의 수를 확인할 수 있습니다. 현재 상태에서 가능한 다음 상태를 탐색하다보면 탐색이 종료되는 시점이 있고, 모든 탐색이 종료되면 우리는 모든 경우의 수를 확인했다고 할 수 있습니다. 다만, 모든 경우의 수를 구하다보면 중복된 계산이 나올 수 있으며 이를 대비하여 메모이제이션 기법을 사용하면 우리는 원하는 제한시간 이내에 답을 구할 수 있습니다.

 

하지만 이 문제를 해결하는 좀 더 효율적인 방법은 따로 있습니다. 바로 가장 큰 숫자부터 K개의 숫자를 크기 순서대로 선택하면 됩니다. 점수를 계산하는 과정을 보면 결국 K개의 숫자에서 K*(K-1)/2 를 뺀 값이 곧 점수라는 걸 알 수 있습니다. 어떤 숫자를 선택하든 빼야하는 숫자는 정해져있기 떄문에 선택되는 K개의 숫자의 합이 클수록 점수가 커지며, K개의 숫자의 합을 가장 크게 만들기 위해서는 큰 숫자 순서대로 K개를 선택하면 됩니다. 따라서 입력받은 N개의 숫자를 오름차순으로 정렬한 다음, 맨 뒤부터 K개의 숫자를 선택하여 합을 구한 후, K*(K-1)/2 값을 빼면 정답을 구할 수 있습니다.

 

소스코드

소스코드는 메모이제이션을 한 소스코드와 정렬을 한 소스코드 2가지를 보여드리겠습니다. 공간/시작 복잡도 상 정렬을 한 소스코드가 훨씬 효율적이라는 걸 보실 수 있습니다.

 

처음은 메모이제이션을 한 소스코드입니다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 5010
#define INF -500000000
using namespace std;
 
int N, K;
int inp[NMAX];
 
int dp[NMAX][NMAX];
int check[NMAX][NMAX];
 
int sv(int idx, int cnt) {
    // 메모이제이션
    if(check[idx][cnt]) return dp[idx][cnt];
    else check[idx][cnt] = 1;
 
 
    // 종료 조건
    if(cnt == 0) return dp[idx][cnt] = 0;
    else if(idx > N) return dp[idx][cnt] = INF;
 
    // 현재 idx 숫자를 선택하는 경우 vs 선택하지 않는 경우
    else {
        int ret=INF;
 
        if(idx+cnt<=N) ret = max(ret, sv(idx+1, cnt));
        ret = max(ret, sv(idx+1, cnt-1) + (inp[idx]-(K-cnt)));
 
        return dp[idx][cnt] = ret;
    }
}
 
int main() {
    // input
    scanf("%d %d", &N, &K);
    for(int i =1;i<=N;i++) scanf("%d", &inp[i]);
 
    // DP
    printf("%d", sv(1, K));
}

 

이번에는 정렬을 한 소스코드입니다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, K, t, ret;
vector< int > inp;
 
int main() {
    // input
    scanf("%d %d", &N, &K);
    for(int i=1;i<=N;i++) {
        scanf("%d", &t);
 
        inp.push_back(t);
    }
 
    // sort
    sort(inp.begin(), inp.end());
 
    for(int cnt=1;cnt<=K;cnt++) {
        ret += inp.back();
        inp.pop_back();
    }
 
    printf("%d", ret - (K*(K-1)/2));
}

후기

문제를 해결할 수 있는 방법이 다양한 문제라고 생각합니다. 물론 정렬을 하는 방법이 가장 효율적이지만 기본적인 메모이제이션을 연습하기에 나름 괜찮은 문제라고 생각합니다.