제 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

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

제 2회 C언어 시험 계획

안녕하세요, kipa00입니다.

SecondMk를 수정 인용:

---

1회 C언어 시험(2013학년도 12월 놀먹 C언어 능력시험)에 이어서,
2회 C언어 시험을 열 계획입니다.
전체적인 시험은 이전 시험과 같습니다만,
이전 시험에서의 경험을 바탕으로 보완을 하고자 합니다.

문법 문항 수 감축

문법을 직접적, 간접적으로 묻는 문제들이 굉장히 많았습니다. 거의 절반이었죠...
게다가, 실제로는 사용될 일이 거의 없는 문법을 묻는 문제들도 있었습니다.
그래서 2회 시험에서는 문법 문항 수를 확실히 줄이겠습니다.
대신, 알고리즘을 묻는 문제들의 비중을 높이겠습니다.

평균 60점대

전 솔직히 1회 시험에서 평균 60점을 예상했습니다만, 평균 40.36점이 나오더군요 ㅋㅋㅋ
출제 중에 출제자들 사이에서 평균 80점 나오면 어떡하냐^[1]는 이야기가 나오기도 했는데,
응시자 최고점이 79점...
문법을 묻는 문제들이 많았던 탓이 큰 것 같습니다.
어려운 문제들, 특히 낚시 문제들은 거의 없도록 하겠습니다.
실제 실력이 드러날 수 있는 시험문제를 만들도록 하겠습니다.

시험 시간

저번 시험에는, 사실 시험 시간이 조절 실패였죠. 20분 추가의 번복이 있었고...
시험 시간이 몇 분이 될지는 아직 모르겠습니다만, 적절하게 조절하도록 하겠습니다.

그리고, 응시자 여러분들께서 29번 문제를 아무도 풀지 못했다는 것에 의문이 좀 드는데...
시험 문제는 컴퓨터를 사용해서 풀어도 아무 상관이 없습니다.
그리고 29번^[2]과 30번은 코딩해서 풀어내지 않으면 답을 찾는 게 사실상 불가능했고요.
다음 시험에서는 컴퓨터를 잘 활용하시길...!

시험 일은 언제가 될지 아직까지 정확히는 모르겠습니다.
시험 문제 출제 이후에 자세한 내용을 발표하도록 하겠습니다.

2013학년도 12월 C언어 능력시험 문제보기 → 여기를 클릭

---

<각주>
[1] 제가 그랬습니다. 그 때 암겨혀님이랑 더 복잡하게 내자고 했던 것도 기억납니다.
[2] 29번 문제, 컴퓨터 없이 풀이: 식을 변형하면 a & b가 0이 되는 것을 찾아주면 된다는 것을 쉽게 알 수 있습니다. 따라서 1 ≤ a < 32, 32 ≤ a < 48, 48 ≤ a일 때 비트를 고려하여 b의 개수를 세어 주신 다음 모두 더하면 됩니다. 자세한 풀이는 여기서 보실 수 있습니다.

덧붙여 말씀드립니다. 저는 제 2회 C언어 29번, 30번 출제자입니다.
이번 29번, 30번 문제도 프로그래밍하셔서 푸셔도 되고, 그렇게 하셔야 합니다.
29번, 30번 문제의 풀이는 먼저 알고리즘을 설명한 뒤,
그에 맞는 코드를 보이는 방식으로 하겠습니다.
그 외 다른 알고리즘 문제들의 풀이가 어떻게 적힐는지 모르겠습니다만,
대체로 이 방식(코드가 필요없으면 알고리즘만 보임)이 될 것 같습니다.

이상입니다. 감사합니다. kipa00