[C언어] 자연수 분할 : 2진수 응용 (백준 9095번 : 1, 2, 3 더하기 풀이)

문제

 

↓ 문제 원문 링크는 아래와 같습니다.

9095번: 1, 2, 3 더하기

 

 

분석

자연수를 분할하는 경우의 수를 묻는 문제입니다.

다른 일반적인 자연수 분할 문제와 다른 특징은 자연수의 분할 순서를 고려하지 않으며, 4 이상의 자연수를 포함하는 분할은 제외한다는 것입니다.

일반적인 자연수 분할 문제라면 수학적으로 계산해서 공식만 구해서 풀기 쉬울테지만, 그렇지 않은 경우이므로 공식을 유도하기 쉽지 않습니다. (숏코딩 순위권 분들의 코드 길이를 보면 이 문제에서도 공식이 존재하기는 합니다.)

 

 

풀이

그렇다면 DP를 이용하여 해결하는 것이 일반적이겠으나, 저는 독립적인 방법으로 이진수를 활용하는 아이디어를 공유하고자 합니다.

예를 들어 n = 7인 경우, 0011100을 2+3+2=7로 보자는 것입니다.

따라서 이 경우에는 2^7 미만의 이진수, 0000000 ~ 1111111까지 중에서 0이나 1이 연속으로 4개 나오는 숫자를 제외하고 카운트 해주면됩니다. (1111100의 경우 5+2로 4 이상의 자연수로 분할되는 경우이므로 제외하자는 것)

그리고 1100011과 0011100은 둘 다 동일하게 2+3+2로 대응이 되므로, 마지막에 count를 2로 나누어주어야 합니다.

 

 

#include<stdio.h>
int a[100] = {}, d;

void f(int n, int time) {
    if(time) f(n/2, --time);
    a[d++] = n%2;
}

int main() {
    int n, pow2 = 1, check = 1, count = 0;
    scanf("%d", &n);
    for(int i=1; i<=n; i++) pow2 *= 2;
    for(int i=0; i<pow2; i++) {
        d = 0;
        f(i, n-1);
        check = 1;
        for(int j=3; j<n; j++) if(a[j] == a[j-1] && a[j] == a[j-2] && a[j] == a[j-3]) check = 0;
        if(check) count++;
    }
    printf("%d", count/2);
}

 

위의 내용대로 작성한 코드의 전문은 위와 같습니다.