4. 연산자 끼워맞추기


연산자 7개를 일일이 끼워맞춰보는 문제다.

루프 7개를 중첩시켜서 돌려서 풀어도 되고, 트리를 구성해서 DFS 등으로 푸는 방법도 있을 것 같다.


그런데, 조금만 생각해보면 루프를 복잡하게 만들 필요가 없다.

연산자가 +/- 둘 밖에 없으니 그냥 각 연산자를 비트 단위로 놓고 단일 루프를 돌려도 된다.


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
    printf("-= plus or minus =-\n");
    int nums[] = { 1, 6, 7, 6, 1, 4, 5 };
    int count = 0;
    for (int i = 0; i < 0x80; i++) {
        int sum = 0;
        int digit = 1;
        for (int j = 0; j < 7; j++) {
            if (i & digit) sum += nums[j];
            else sum -= nums[j];
            digit <<= 1;
        }
        if (sum == 0) {
            digit = 1;
            for (int j = 0; j < 7; j++) {
                printf("%c", (i & digit) ? '+' : '-');
                digit <<= 1;
                printf("%d", nums[j]);
            }
            printf(" = 0\n");
            count++;
        }
    }
    printf("%d fomulars are found\n", count);
    return 0;
}


이렇게 돌려보면 총 4개의 수식이 나온다.


-= plus or minus =-
+1+6+7-6+1-4-5 = 0
+1-6+7+6+1-4-5 = 0
-1+6-7-6-1+4+5 = 0
-1-6-7+6-1+4+5 = 0
4 fomulars are found



5. 비트 반전


이건 뭐 문제랄 것도 없다.

이것 역시 못 풀면 이 바닥 진입 금지.


#include <stdio.h>
#include <stdlib.h>

unsigned int InverseBits(unsigned int value)
{
    //return 0xffffffff ^ value;    //이렇게 써도 되고,
    //return 0xffffffff - value;    //이렇게 써도 됨
    return ~value;
}

int main(int argc, char* argv[])
{
    static unsigned int value = 123456789;

    printf("-= inverse bits =-\n");
    printf("InverseBits(%u) = %u\n", value, InverseBits(value));
    return 0;
}


32bit unsigned integer라고 명시했기 때문에 아무 연산자나 쓰면 된다.

심지어는 빼기도 상관 없…


결과는 아래와 같다.


-= inverse bits =-
InverseBits(123456789) = 4171510506



+ Recent posts