[도전 6일차] 채점 - KOI 고등부 풀이

문제 : BOJ 6989 채점

백준 채점 풀이

KOI 2008 고등부 1번

문제 링크

사용 알고리즘 : DP, 비트마스킹

문제 설명 :

 n(n<=150)개의 문제가 주어집니다. 문제들에는 각각 0~100까지의 배점이 부여되어 있습니다.

이 시험지는 맞은 문제들이 연속해 있을 때 더 많은 점수를 부여합니다.

sum(i,j)를 i번째 문제 부터 j번째 문제까지 배점의 합 (연속합),

score(i,j) 를 i번째 문제부터 j번째 문제까지 맞았을 때 받는 점수로 정의할 때 

score(i,j) = score( i, j-1 ) + sum(i,j) 가 만족됩니다.

 

쉽게 말하면 한 문제를 맞고 그 뒤에 푼 문제들을 계속 맞으면 앞에 푼 문제의 점수가 계속 더해집니다. 

아래는 문제의 설명입니다.

출처 : 백준 6989

풀이:

score(i,j) 는 다음 점화식을 사용하여 쉽게 구할 수 있다.

score(i,j) = score( i, j-1 ) + sum(i,j)

 

다음과 같은 DP를 정의하자.

DP[i][j] = i번 문제까지 고려했을 때 점수 j를 만들 수 있으면 true, 없으면 false

init : DP[0][0] =true; 
DP[1][arr[1]] = true; DP[1][0] = true; //굳이 필요 없으나 이해를 위해 추가함.

 

t부터 i번째 문제까지 연속해서 맞았을 때 k를 t의 최솟값이라고 하자.

쉽게 설명하면 XXOOO에서

i=5일 때 t는 3,4,5가 될 수 있고, 최솟값 k는 3이다.

만약 i번 문제를 틀렸다면 k=i+1 이다.

 

DP[i][j]는  k ( 1<=k<=i+1) 에 대해서

k<=2 이면 score(k, i) == j 

k>2 이면 k-1번째 문제를 틀렸다는 뜻이므로 DP[k-2][ j - score(k,i)] 

중 하나라도 true 이면 DP[i][j]=true 이다.

 

문제를 살펴보면 i의 최대값은 150, j의 최대값은 100 * (150*151)/2 ~= 1200000 (120만) 정도다.

120만 * 150 > 1억으로, 일반적인 bool 배열을 선언하면 메모리초과가 발생한다.

 

그래서 우리는 이때 2가지 방법을 사용하여 메모리 초과를 탈출할 수 있다.

1. 비트마스킹

unsigned int DP[i][j/32] 배열을 선언하여 j%32 비트를 토글링 한다. (혹은 unsigned long long 배열과 64bit 토글링)

 

2. C++ STL Bitset 사용

std::bitset<1200000> DT[160] 을 사용한다. (bitset 한 비트는 1bit, bool 자료형은 1byte를 사용한다.)

bitset은 쉽게 말해 bool 배열과 동일하며 추가적인 기능을 제공한다.

bool a[160][1000] 과 bitset<1000> a[160]가 동일하다고 생각하면 된다.

bitset에도 여러 내장 함수가 있으므로 궁금한 사람들은 찾아보기를 권한다.

사용법은 배열과 동일하다. a[i][j] = 0/1로 i번째 비트셋의 j번째 비트를 다룰 수 있다.

 

1번 방법은 구현이 까다롭지만 DP를 갱신하는데 있어 빠른 속도를 보여주고

2번 방법은 느리지만 구현이 쉽다. 

두 방법 모두 사용 메모리는 비슷하다.

 

이 글에서는 2번 방법으로 구현한다. 1번 방법이 궁금하신 분은 2번 방법으로 구현 후 필자의 코드는 공개가 되어 있으니 시간이 가장 빠른 코드를 참고해보기 바란다.

 

본 코드에서는 DP를 아래에서 위로 채워 나가는 형식으로 구현했다. 

DP[i][j]를 다른 DP를 이용해 채우는 것이 아니라, 이미 채워진 DP[i][j]를 이용해 다른 DP를 채운다는 뜻이다. 

(이 말이 이해가 잘 안되면 코드를 보고 파악하는 것도 좋다.)

 

첨언하자면, 2번 방법으로 구현한 DP는 정직하게 계산했을 시 시간초과가 나는게 맞다.

$150\times150\times1200000 > 10^8$

 

다만 bitset의 사기성으로 인해 200억에 달하는 연산량이 1초 안에 동작한다.

bitset의 사기성이 들어나는 부분은 바로 시프트 연산이다. 

dp[i]는 이제 1200000개의 비트를 담긴 비트셋이다.

이제 dp[i]를 어떤 k에 대해 dp[k-2]를 이용해 채운다.

 

dp식을 살펴보면 dp[i]의 x번째 칸을 dp[k-2]의 (x-score(k,i))번째 칸을 이용해 채우는 것을 알 수 있다.

 

모든 x에 대해 score(k,i)는 일정하므로 이는 dp[k-2]를 score(k,i)만큼 땡겨서

dp[i]에 대해 OR 연산을 한다고 생각할 수 있다.

 

따라서 $dp[i] |= dp[k-2] << score[k][i]$라는 식으로

하나의 반복문을 압축할 수 있다.

 

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
using namespace std;
const int N = 152;
int n,k,arr[N],sum[N],score[N][N]; 
//score[i][j] : i번부터 j번까지 맞았을 경우의 점수
//if j>i : then score [j][i] = 0 
//100+200+ .... + 15000 < 1140000
bitset<1140000> DT[N];
void input(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>arr[i],sum[i]=sum[i-1]+arr[i];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            score[i][j]=score[i][j-1]+sum[j]-sum[i-1];
    cin>>k;
}
void solve(){
    if(k>score[1][n]){
        cout<<k;
        return;
    }
    DT[0].set(0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i+1;j++){
        // j부터 i번째 문제까지 연속해서 맞았을 가능한 점수
        // j=i+1 이면 i번째 문제를 틀린 것. 
            if(j<=2)
                DT[i].set(score[j][i]);
            else
                DT[i] |= (DT[j-2]<<score[j][i]);
        }
    }
    int ans=k;
    while(DT[n].test(ans)) ans++;
    cout<<ans;
}
int main(){
    input();
    solve();
    return 0;
}