제 1회 놀먹 C언어 능력 시험 29번 문제 풀이

코드 풀이는 간단합니다.

#include <stdio.h>

int main() {

    int a, b, cnt = 0;
    for (a=1; a<50; ++a) {
        for (b=1; b<50; ++b) {
            if ((a + b) == (a | b)) {
                ++cnt;
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}
// 516 출력

코드를 작성하지 않고 푸는 풀이는 다음과 같습니다.

우선 식을 변형하겠습니다. 이진법의 계산과 받아올림의 원리에 따라

a + b = (a ^ b) + (a & b) << 1

모든 양수 c에 대해서 c << 1은 c * 2이므로,

a + b = (a ^ b) + (a & b) * 2 = (a ^ b) + (a & b) + (a & b)

f(a, b) = (a ^ b) + (a & b)라고 잡고 a, b에 따른 계산을 해 주면

f | 0 | 1
--+---+---
0 | 0 | 1
--+---+---
1 | 1 | 1

f(a, b) = a | b라는 결론을 간단하게 내릴 수 있으므로,
주어진 조건문은 a | b == (a | b) + (a & b)가 되므로
그것을 a & b == 0으로 간단하게 바꿀 수 있습니다.

a의 비트가 xyz라고 합시다. 만약 x가 0이라면, b의 x 자리에는 임의의 비트(2가지의 경우)가 올 수 있습니다. 만약 x가 1이라면, b의 x 자리에는 반드시 0 비트(1가지의 경우)가 와야 합니다. 따라서 a가 정해져 있을 때, b가 될 수 있는 개수는 2^{(a의 0인 비트의 개수)}개입니다.

i) 1 ≤ a < 32, 1 ≤ b < 32(XXXXX, a 기준으로 변하는 비트 5개)인 경우에는,

1) 0이 하나도 없음: ₅C₀2⁰ = 1
2) 0이 하나 있음: ₅C₁2¹ = 10
3) 0이 두 개 있음: ₅C₂2² = 40
4) 0이 세 개 있음: ₅C₃2³ = 80
5) 0이 네 개 있음: ₅C₄2⁴ = 80
각각의 경우에서, b ≠ 0이므로 이 경우 31가지를 제외하면
합: 1 + 10 + 40 + 80 + 80 - 31 = 180

ii) 1 ≤ a < 32, 32 ≤ b < 48(10XXXX, b 기준으로 변하는 비트 4개)인 경우에는,

1) 0이 하나 있음: ₄C₀2¹ = 2
2) 0이 두 개 있음: ₄C₁2² = 16
3) 0이 세 개 있음: ₄C₂2³ = 48
4) 0이 네 개 있음: ₄C₃2⁴ = 64
4) 0이 다섯 개 있음: ₄C₄2⁵ = 32
각각의 경우에서, b ≠ 0이므로 이 경우 16가지를 제외하면
합: 2 + 16 + 48 + 64 + 32 - 16 = 146

iii) 1 ≤ a < 32, 48 ≤ b < 50(b 기준)인 경우에는,

1) b = 48(110000₍₂₎) : 2⁴ - 1 = 15
2) b = 49(110001₍₂₎) : 2³ - 1= 8
각각의 경우에서, b ≠ 0이므로 이 경우 2가지를 제외하면
합: 16 + 8 - 2 = 22

iv) 32 ≤ a < 48인 경우에는 32 ≤ b인 경우가 존재할 수 없으므로, a와 b를 바꾸면 ii)와 같아지고, 순서만 뒤바뀐 것입니다. 따라서 개수는 ii)에서 구했던 그대로 146
v) 48 ≤ a ≤ 50인 경우에는 32 ≤ b인 경우가 존재할 수 없으므로, a와 b를 바꾸면 iii)와 같아지고, 순서만 뒤바뀐 것입니다. 따라서 개수는 iii)에서 구했던 그대로 22

모두 더하면, 180 + 146 + 22 + 146 + 22 = 516

출제진들은 여러분들이 당연히 프로그래밍할 거라고 생각했습니다.
일단 이렇게도 풀 수 있지만 이렇게 풀면 정말로 약 빤거죠 저도 쓰면서 여러번 실수했는데
고, 불가능한 건 없습니다. 혹시 풀이가 이해 안 되시면 댓글 달아주세요.