좋은 수( BOJ 5624 )

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

5624번: 좋은 수

 

문제 파악하기

N개의 정수 중 자신보다 앞에 있는(왼쪽에 위치한) 3개의 숫자들의 합으로 나타낼 수 있는 숫자의 개수를 구하는 문제입니다. N의 범위가 최대 5,000이기 때문에 3개의 숫자를 모두 확인할 수는 없습니다. 맨 첫 번째 숫자부터 하나씩 배열에 체크하면서 각각의 숫자를 만들 수 있는지 여부를 체크하면 되며, 이 경우 동적 프로그래밍 기법을 활용할 수 있습니다.

 

문제 해결하기

우리는 이 문제를 해결하기 위해서 필요한 정보는 특정 숫자를 앞선 숫자 3개의 합으로 만들 수 있는지 여부입니다. 따라서 이렇게 2가지 정보(0, 1)만 필요한 경우에는 비트 기반 자료구조를 활용하여 저장하고 계산할 수 있으며, 여기서는 bitset 자료구조를 활용하도록 하겠습니다. 우리가 궁금한 자료는 숫자를 3개 사용하여 현재 숫자인 K를 만들 수 있는지 여부입니다. 그렇기에 우리는 숫자 1개 ~ 3개 더한 결과를 저장할 bitset 3개를 만들어야 합니다. 그리고 숫자를 하나씩 더하면서 나온 모든 결과를 갱신해주면 문제를 해결할 수 있습니다.

 

우선, 현재 숫자 K는 3개의 숫자를 더한 결괏값에서 확인할 수 있습니다. 그리고 K를 총 3번 더해주면서 각각의 결과를 만들어둔 bitset에 저장하여 다음 숫자를 확인할 때 활용할 수 있습니다. 여기서 중요한 점은 K를 더해준다는 건 결국 비트들은 옮겨준다는 의미기에 비트 시프트 연산(<<, >>)을 사용한다는 점입니다. 비트 시프트 연산을 활용하면 하나씩 옮기는 연산보다 훨씬 빠르기에 충분히 문제를 해결할 수 있습니다.

 

자세한 소스코드는 아래와 같습니다.

 

소스코드

#import <stdio.h>
#import <bitset>
#define NMAX 200010
using namespace std;
 
int N, t, cnt;
bitset< NMAX*2 > check[4];
 
int main() {
    scanf("%d", &N);
 
    check[0][NMAX] = 1;
    for(int i=1;i<=N;i++) {
        scanf("%d", &t);
 
        cnt += check[3][t+NMAX];
 
        for(int j=1;j<=3;j++) {
            if(t >= 0) check[j] = check[j] | (check[j-1]<<t);
            else check[j] = check[j] | (check[j-1]>>-t);
        }
    }
 
    printf("%d", cnt);
 
}
/*
5
-1 2 -2 -1 5
ans: 1
 
4
100000 100000 -100000 100000
ans: 1
*/

후기

등장 횟수를 효율적으로 기록하여 활용하는 동적 프로그래밍 문제입니다. 문제 자체를 이해하기는 어렵지 않기에 동적 프로그래밍을 연습하기에 적절한 문제라고 생각합니다.