3 - 2024 KOI 1교시 고등부 풀이 정리

2024 KOI 1교시 고등부 풀이 정리

이 문서는 2024 - 고등부 기출문제를 바탕으로, 고등학생 기준에서 다시 읽기 쉽게 정리한 학습용 풀이 노트입니다. 2024 고등부 자료는 공식 해설을 포함하고 있으므로, 핵심 아이디어는 해설을 따르되 문장과 계산 흐름을 더 또렷하게 정리했습니다.

1. 두 개씩 곱하기

문제 한눈에 보기

$1,2,3,4,5,6$에서 서로 다른 두 수를 골라 곱한 값을 모두 더하는 문제입니다.

답

$175$

핵심 개념

$(x_1+x_2+\cdots +x_6{)}^2$를 전개하면 서로 다른 두 수의 곱이 정확히 두 번씩 나타납니다.

왜 이 생각을 먼저 해야 하는지

모든 쌍을 직접 적어도 되지만, 제곱식 전개를 쓰면 한 줄로 끝납니다.

단계별 풀이

1. 전체 합은 $1+2+3+4+5+6=21$입니다.
2. 따라서 $21^2=441$입니다.
3. 이 안에는 제곱항 $1^2+2^2+\cdots +6^2=91$도 포함되어 있습니다.
4. 그래서 서로 다른 두 수의 곱이 두 번씩 들어간 합은 $441-91=350$입니다.
5. 우리가 원하는 값은 한 번씩만 센 것이므로 $350/2=175$입니다.

헷갈리기 쉬운 점

전개식에서는 ab와 ba가 둘 다 나오므로 마지막에 $2$로 나누어야 합니다.

2. 진법 변환

문제 한눈에 보기

16진수 A6E4F3을 8진수로 바꾼 뒤, 나타나는 숫자들의 합을 구하는 문제입니다.

답

$31$

핵심 개념

16진수는 2진수 4자리, 8진수는 2진수 3자리와 정확히 대응합니다.

왜 이 생각을 먼저 해야 하는지

16진수에서 8진수로 바로 바꾸려 하면 자리 맞춤에서 실수하기 쉽습니다. 2진수를 중간 다리로 쓰는 것이 가장 안전합니다.

단계별 풀이

1. A6E4F3을 2진수로 바꾸면 1010 0110 1110 0100 1111 0011입니다.
2. 공백을 없애면 $101001101110010011110011$입니다.
3. 이를 왼쪽부터 3자리씩 끊기 좋게 010 100 110 111 001 001 111 011으로 정리합니다.
4. 각 묶음을 8진수로 읽으면 2 4 6 7 1 1 7 3입니다.
5. 따라서 8진수는 $24671173$이고, 자리수 합은 $2+4+6+7+1+1+7+3=31$입니다.

헷갈리기 쉬운 점

맨 앞 자리가 3비트가 안 맞으면 왼쪽에 $0$을 붙여도 값은 변하지 않습니다.

3. 최소 신장 트리

문제 한눈에 보기

주어진 가중치 그래프의 최소 신장 트리 가중치 합을 구하는 문제입니다.

답

$99$

핵심 개념

가중치가 작은 간선부터 넣되, 사이클이 생기면 건너뛰는 크루스칼 알고리즘을 쓰면 됩니다.

왜 이 생각을 먼저 해야 하는지

최소 신장 트리는 간선 선택 순서가 핵심입니다. 가장 표준적인 방법이 크루스칼입니다.

단계별 풀이

1. 가중치가 작은 간선부터 차례대로 봅니다.
2. $10$, $12$, $14$, $16$인 간선은 모두 서로 다른 연결 요소를 잇기 때문에 넣을 수 있습니다.
3. 다음 가중치 $18$인 간선은 이미 연결된 부분 안에서 원을 만들므로 제외합니다.
4. 가중치 $22$인 간선을 넣어 두 덩어리를 더 크게 연결합니다.
5. 가중치 $24$인 간선도 사이클을 만들므로 제외합니다.
6. 가중치 $25$인 간선을 넣으면 모든 정점이 하나로 연결됩니다.
7. 실제로 선택된 간선은 $AF(10),CD(12),BG(14),BC(16),ED(22),FE(25)$이고, 합은 $10+12+14+16+22+25=99$입니다.

헷갈리기 쉬운 점

가중치가 작다고 무조건 넣는 것이 아닙니다. 이미 연결된 곳끼리 잇는 간선은 빼야 합니다.

4. 기사, 도둑, 바보

문제 한눈에 보기

기사는 항상 참, 도둑은 항상 거짓, 바보는 아무 말이나 할 수 있을 때, 세 사람 A, B, C의 역할 배정을 모두 세는 논리 퍼즐입니다.

답

$4$

핵심 개념

가장 강한 문장부터 보면 경우 수가 급격히 줄어듭니다.

왜 이 생각을 먼저 해야 하는지

C: 나는 도둑이다 같은 문장은 스스로를 직접 가리키므로 참/거짓 판정이 매우 강합니다.

단계별 풀이

1. C가 기사라면 나는 도둑이다가 참이어야 하는데, 기사와 도둑은 동시에 될 수 없으므로 불가능합니다.
2. C가 도둑이라면 그 문장은 거짓이어야 하는데, 나는 도둑이다는 참이므로 역시 불가능합니다.
3. 따라서 C는 반드시 바보입니다.
4. 그러면 A의 말 우리 중 한 명 이상이 바보이다는 실제로 참입니다.
5. 따라서 A는 기사이거나 바보일 수는 있지만, 거짓만 말하는 도둑일 수는 없습니다.
6. 이제 B: A는 바보가 아니다를 봅니다.
7. A가 기사이면 이 문장은 참이므로 B는 기사 또는 바보입니다. 이 경우 $2$가지입니다.
8. A가 바보이면 이 문장은 거짓이므로 B는 도둑 또는 바보입니다. 이 경우도 $2$가지입니다.
9. 합치면 전체 경우 수는 $4$가지입니다.

헷갈리기 쉬운 점

바보는 참을 말해도 되고 거짓을 말해도 됩니다. 그래서 바보가 가장 경우의 수를 많이 남깁니다.

5. 참으로 만들기

문제 한눈에 보기

명제식 $((p\vee q)\to (\neg q\vee r))\to ((\neg p\vee s)\wedge \neg r)$가 참이 되도록 하는 $(p,q,r,s)$의 개수를 세는 문제입니다.

답

$7$

핵심 개념

복잡한 식은 먼저 간단한 동치식으로 줄인 뒤 경우를 세면 됩니다.

왜 이 생각을 먼저 해야 하는지

16가지를 전부 대입하는 것도 가능하지만, 논리식을 정리하면 한 번에 구조가 드러납니다.

단계별 풀이

1. 먼저 $(p\vee q)\to (\neg q\vee r)$를 정리합니다.
2. 이는 $\neg (p\vee q)\vee (\neg q\vee r)$와 같고, 다시 정리하면 $\neg q\vee r$와 같습니다.
3. 따라서 전체 식은 $(\neg q\vee r)\to ((\neg p\vee s)\wedge \neg r)$입니다.
4. 다시 함축을 풀면 $\neg (\neg q\vee r)\vee ((\neg p\vee s)\wedge \neg r)$입니다.
5. $\neg (\neg q\vee r)=q\wedge \neg r$이므로, 전체 식은 $(q\wedge \neg r)\vee ((\neg p\vee s)\wedge \neg r)$입니다.
6. $\neg r$을 묶으면 $\neg r\wedge (q\vee \neg p\vee s)$가 됩니다.
7. 즉 이 식이 참이 되려면 먼저 r = 거짓이어야 하고, 동시에 $q\vee \neg p\vee s$가 참이어야 합니다.
8. r = 거짓으로 고정하면 $(p,q,s)$는 $2^3=8$가지인데, 그중 p=참, q=거짓, s=거짓 한 가지에서만 $q\vee \neg p\vee s$가 거짓입니다.
9. 따라서 정답은 $8-1=7$입니다.

헷갈리기 쉬운 점

함축 $A\to B$는 $\neg A\vee B$로 바꾸는 순간 계산이 쉬워집니다.

6. 인버전의 개수

문제 한눈에 보기

각 위치 $i$에 대해, 왼쪽에서 자기보다 큰 수의 개수 $c_i$가 주어졌을 때 원래 순열을 복원하는 문제입니다.

답

$43728165$

핵심 개념

주어진 $c_i$는 순열의 Lehmer code와 같은 역할을 합니다. 뒤에서부터 복원하면 됩니다.

왜 이 생각을 먼저 해야 하는지

앞에서부터는 아직 모르는 수가 너무 많지만, 뒤에서부터는 남은 수 집합만 보고 바로 고를 수 있습니다.

단계별 풀이

1. 처음 남아 있는 수는 $1,2,3,4,5,6,7,8$입니다.
2. $c_8=3$이라는 말은 $a_8$보다 큰 수가 왼쪽에 3개 있다는 뜻이므로, 남은 수 중 4번째로 큰 수를 골라야 합니다. 따라서 $a_8=5$입니다.
3. 이제 남은 수는 $1,2,3,4,6,7,8$입니다. $c_7=2$이므로 3번째로 큰 수를 골라 $a_7=6$입니다.
4. $c_6=5$이므로 남은 수 중 6번째로 큰 수, 즉 $a_6=1$입니다.
5. 같은 일을 계속하면
6. $a_5=8$, $a_4=2$, $a_3=7$, $a_2=3$, $a_1=4$가 됩니다.
7. 따라서 원래 순열은 $4,3,7,2,8,1,6,5$이고, 이어 붙이면 $43728165$입니다.

헷갈리기 쉬운 점

$c_i$는 왼쪽의 큰 수 개수이므로, 뒤에서 복원할 때는 c_i+1번째로 큰 수를 선택해야 합니다.

7. 화살표 따라가기

문제 한눈에 보기

각 정점의 나가는 간선이 하나씩만 있는 함수 그래프에서, $101$번 이동한 뒤 $5$ 또는 $9$에 도착하는 시작점들을 모두 더하는 문제입니다.

답

$55$

핵심 개념

이런 그래프는 반드시 어떤 사이클로 들어갑니다. 긴 이동은 결국 사이클 길이의 나머지 문제로 바뀝니다.

왜 이 생각을 먼저 해야 하는지

$101$번을 직접 따라가는 것보다, 먼저 어떤 사이클에 들어가는지 보는 편이 훨씬 빠릅니다.

단계별 풀이

1. 그림을 따라가면 $9\to 2\to 5\to 4\to 8\to 9$라는 길이 $5$의 사이클이 있습니다.
2. 따라서 사이클에 들어간 뒤에는 $101$번 이동과 $101\mathrm{mod}5=1$번 이동이 같은 효과를 냅니다.
3. 이제 각 시작점이 사이클로 들어가기까지의 앞부분만 짧게 추적하면 됩니다.
4. 확인해 보면 $101$번 뒤에 $5$ 또는 $9$에 도착하는 시작점은 $2,3,6,8,10,12,14$입니다.
5. 합은 $2+3+6+8+10+12+14=55$입니다.

헷갈리기 쉬운 점

사이클 길이만 보는 것은 사이클에 들어간 뒤에만 가능합니다. 들어가기 전 꼬리 부분은 따로 확인해야 합니다.

8. 비트 연산의 합

문제 한눈에 보기

A, B가 $0$부터 $7$까지일 때, $A\mathrm{AND}B$, $A\mathrm{OR}B$, $A\mathrm{XOR}B$의 값을 모든 경우에 대해 더하는 문제입니다.

답

$672$

핵심 개념

비트 연산의 합은 비트별로 독립적으로 계산할 수 있습니다.

왜 이 생각을 먼저 해야 하는지

정수 전체를 한꺼번에 보면 192가지를 모두 다뤄야 하지만, 비트별로 보면 똑같은 패턴이 3번 반복됩니다.

단계별 풀이

1. $0$부터 $7$까지는 3비트 수이므로, 각 비트 자리 $1$, $2$, $4$를 따로 봅니다.
2. 한 비트에서 $(0,0)$이면 $\mathrm{AND}+\mathrm{OR}+\mathrm{XOR}=0+0+0=0$입니다.
3. $(0,1)$, $(1,0)$, $(1,1)$이면 항상 $\mathrm{AND}+\mathrm{OR}+\mathrm{XOR}=2$입니다.
4. 즉 한 비트의 기여는 “둘 다 0인 경우만 0, 나머지는 모두 2”입니다.
5. $0$부터 $7$까지의 수 8개 중 절반인 4개는 그 비트가 0이고, 나머지 4개는 1입니다.
6. 따라서 $(A,B)$ 64쌍 중 둘 다 0인 쌍은 $4\times 4=16$개이고, 적어도 하나가 1인 쌍은 $64-16=48$개입니다.
7. 한 비트 자리의 총 기여는 $48\times 2\times (\text{그 비트의 값})$입니다.
8. 세 비트를 합치면 $48\times 2\times (1+2+4)=96\times 7=672$입니다.

헷갈리기 쉬운 점

AND, OR, XOR를 각각 따로 세어도 되지만, 비트 한 자리에서 셋의 합이 바로 $0$ 또는 $2$가 된다는 점을 이용하면 훨씬 짧아집니다.

9. 최소 힙 조건

문제 한눈에 보기

주어진 트리에 $1$부터 $13$까지를 배치하되, 부모가 자식보다 항상 작아지게 하는 경우의 수를 세는 문제입니다.

답

$432$

핵심 개념

최소 힙에서는 각 서브트리의 루트가 그 서브트리에서 가장 작은 값을 가져야 합니다. 그래서 “어떤 값 집합이 어느 서브트리로 가는가”를 먼저 세면 됩니다.

왜 이 생각을 먼저 해야 하는지

숫자를 직접 배치하려 들면 복잡하지만, 서브트리 크기만 보면 조합 곱으로 정리됩니다.

단계별 풀이

1. 전체 루트는 반드시 가장 작은 수 $1$을 받아야 합니다.
2. 남은 $12$개의 수를 왼쪽 크기 $3$짜리 서브트리와 오른쪽 크기 $9$짜리 서브트리로 나누는 방법 수는 $C(12,3)$입니다.
3. 왼쪽 3개짜리 서브트리에서는 그 3개 중 가장 작은 수가 서브트리 루트로 가고, 나머지 두 수는 두 잎에 아무렇게나 갈 수 있으므로 $2$가지입니다.
4. 오른쪽 9개짜리 서브트리에서도 가장 작은 수가 그 서브트리 루트로 갑니다.
5. 그 아래 두 개의 4개짜리 서브트리에 남은 $8$개의 수를 나누는 방법은 $C(8,4)$입니다.
6. 각 4개짜리 서브트리는 루트 1개와 잎 3개 구조이므로, 가장 작은 수가 루트에 가고 나머지 $3$개는 자유롭게 섞여 $3!=6$가지입니다.
7. 따라서 전체 경우의 수는 $C(12,3)\times 2\times C(8,4)\times 6\times 6=1108800$입니다.
8. 문제에서 이 값이 $12!/k$라고 했으므로
9. $k=12!/1108800=432$입니다.

헷갈리기 쉬운 점

$13!$가 아니라 $12!$이 나오는 이유는 전체 루트에 $1$이 고정되어 있기 때문입니다.

10. 동전

문제 한눈에 보기

4원 동전과 7원 동전을 이용해, 거스름돈까지 포함한 총 동전 수를 6개 이하로 제한할 때 만들 수 있는 금액의 개수를 세는 문제입니다.

답

$37$

핵심 개념

거스름돈까지 허용되므로 낸 돈 - 받은 돈 = 물건 값의 꼴로 봐야 합니다.

왜 이 생각을 먼저 해야 하는지

단순히 $4a+7b$만 보면 놓치는 값이 많습니다. 거슬러 받는 동전도 식에 들어가야 합니다.

단계별 풀이

1. 값을 $n=4a+7b-4c-7d$로 나타냅니다.
2. 여기서 $a+b+c+d\le 6$이어야 합니다.
3. 만들 수 있는 값의 범위는 문제에서 $1$부터 $42$까지입니다.
4. 동전 수가 최대 6개뿐이므로, 가능한 조합을 표로 정리하거나 간단히 전부 확인할 수 있습니다.
5. 그렇게 세어 보면 만들 수 없는 값은 $34,37,38,40,41$ 다섯 개뿐입니다.
6. 따라서 만들 수 있는 값의 개수는 $42-5=37$입니다.

헷갈리기 쉬운 점

예를 들어 10원 = 7+7-4처럼, 원래 값보다 크게 내고 일부를 거슬러 받는 표현도 허용됩니다.

11. 로봇과 그래프

문제 한눈에 보기

같은 정점이라도 홀수 번째 방문이면 파란 간선, 짝수 번째 방문이면 빨간 간선을 따라가는 로봇이 X에 처음 도착할 때까지의 이동 횟수를 구하는 문제입니다.

답

$1138$

핵심 개념

정점 이름만으로는 상태가 결정되지 않습니다. 정점 + 방문 횟수의 홀짝을 하나의 상태로 보아야 합니다.

왜 이 생각을 먼저 해야 하는지

A에 다시 왔다고 해도 첫 방문인지 둘째 방문인지에 따라 다음 간선이 달라집니다.

단계별 풀이

1. 각 정점을 홀수 방문 상태와 짝수 방문 상태 두 개로 나눕니다.
2. 그러면 이 문제는 각 상태에서 다음 상태가 하나씩 정해지는 함수 그래프 문제가 됩니다.
3. 시작 상태는 $A(1)$입니다.
4. 이제 상태 그래프 위에서 정해진 규칙대로 한 칸씩 추적하면 됩니다.
5. 이 과정을 끝까지 따라가면 로봇은 $1138$번째 이동에서 처음 X에 도착합니다.

헷갈리기 쉬운 점

원래 그래프에는 정점이 하나여도, 상태 그래프에서는 같은 정점이 두 번 등장합니다.

12. 부분집합의 합

문제 한눈에 보기

가치가 $1$부터 $8$인 아이템이 각각 $c_1,c_2,\cdots ,c_8$개 있고, 부분집합 합의 개수 $s_0$부터 $s_8$까지가 주어질 때 $c_i$들을 복원하는 문제입니다.

답

$43614952$

핵심 개념

생성함수

$P(x)=(1+x{)}^{c_1}(1+x^2{)}^{c_2}\cdots (1+x^8{)}^{c_8}$

의 $x^k$ 계수가 바로 $s_k$입니다.

왜 이 생각을 먼저 해야 하는지

가치가 모두 양수이므로 $x^k$의 계수는 $c_1$부터 $c_k$까지만 영향을 줍니다. 그래서 작은 차수부터 차례대로 $c_i$를 복원할 수 있습니다.

단계별 풀이

1. $x^1$의 계수는 오직 가치 $1$ 아이템에서만 나오므로 $c_1=s_1=4$입니다.
2. $x^2$의 계수는 $1+1$ 또는 $2$에서만 나오므로 $C(c_1,2)+c_2=9$입니다.
3. 따라서 $C(4,2)+c_2=9$, 즉 $6+c_2=9$이므로 $c_2=3$입니다.
4. $x^3$의 계수는 $1+1+1$, $1+2$, $3$에서 나오므로
5. $C(4,3)+4\cdot 3+c_3=22$입니다.
6. 즉 $4+12+c_3=22$이어서 $c_3=6$입니다.
7. 같은 방식으로 $x^4$의 계수를 비교하면 $c_4=1$이 나옵니다.
8. 이어서 $x^5,x^6,x^7,x^8$의 계수를 차례대로 비교하면 $c_5=4$, $c_6=9$, $c_7=5$, $c_8=2$를 얻습니다.
9. 따라서 $c_1{c}_2\cdots c_8=43614952$입니다.

헷갈리기 쉬운 점

한 번에 식 전체를 풀려고 하지 말고, $x^1$, $x^2$, $x^3$처럼 차수를 올려 가며 순서대로 푸는 것이 핵심입니다.

13. 스탬프

문제 한눈에 보기

주어진 모양의 스탬프를 적절히 눌러서 모든 칸의 숫자를 $0$으로 만드는 구성 문제입니다.

답

해설의 핵심 전략은 왼쪽에서 오른쪽으로, 위에서 아래로 훑으면서 각 칸을 더 이상 누를 수 없을 때까지 처리하는 것입니다.

핵심 개념

앞에서 지난 칸은 뒤쪽 결정을 해도 다시 고치기 어렵습니다. 그래서 행 우선 스캔 그리디가 자연스럽습니다.

왜 이 생각을 먼저 해야 하는지

이 문제는 정답 배치가 하나가 아니라, 어떤 순서로 누를지를 정하는 문제가 핵심입니다. 해설이 제시한 순서가 바로 안정적인 그리디입니다.

단계별 풀이

1. 격자를 왼쪽에서 오른쪽, 위에서 아래 순서로 봅니다.
2. 현재 보고 있는 칸을 기준으로, 조건을 깨지 않는 범위에서 가능한 만큼 스탬프를 누릅니다.
3. 한 칸을 넘기면 그보다 앞선 칸은 다시 조절하기 매우 어려우므로, 그 칸을 지나가기 전에 필요한 처리를 끝내야 합니다.
4. 이 과정을 모든 칸에 대해 반복하면 결국 전체 격자를 $0$으로 만들 수 있습니다.
5. 실제 배치는 해설 그림의 예시와 같이 잡으면 됩니다.

헷갈리기 쉬운 점

스탬프를 뒤집거나 돌릴 수 없습니다. 허용된 방향 그대로만 써야 합니다.

14. 제자리

문제 한눈에 보기

제자리에 있는 카드 중 하나를 골라 맨 앞으로 보내는 일을 반복할 때, 총 이동 횟수를 최대화하는 문제입니다.

답

최대 이동 횟수는 $31$이고, 항상 움직일 수 있는 카드 중 가장 앞에 있는 카드를 고르면 됩니다.

핵심 개념

앞 카드를 먼저 움직여야 뒤쪽 카드들의 제자리 성질을 더 오래 보존할 수 있습니다.

왜 이 생각을 먼저 해야 하는지

뒤쪽 카드를 먼저 당기면 앞부분 구조가 크게 흔들리지만, 앞쪽 카드를 먼저 움직이면 뒤쪽의 선택지를 더 오래 남길 수 있습니다.

단계별 풀이

1. 매 순간 이동 가능한 카드는 제자리에 있으면서 숫자가 $2$ 이상인 카드들입니다.
2. 이들 중에서 가장 앞 카드를 고르는 전략을 씁니다.
3. 이 선택은 뒤쪽 카드들의 상대적 구조를 가장 덜 망가뜨립니다.
4. 따라서 앞으로도 더 많은 제자리 카드를 남겨 두는 방향으로 작동합니다.
5. 해설이 증명하는 최적 전략이 바로 이 그리디이고, 그때 최대 이동 횟수는 $31$입니다.

헷갈리기 쉬운 점

값이 가장 큰 카드를 고르는 것이 아닙니다. 위치가 가장 앞인 카드를 고르는 것이 핵심입니다.

15. 숫자 카드

문제 한눈에 보기

79장의 카드에서 연속한 5장씩 15번 지워 4장을 남길 때, 남은 4장을 이어 만든 수를 최소화하는 문제입니다.

답

$5476$

핵심 개념

끝에 남는 4장은 원래 위치의 나머지 클래스가 사실상 정해집니다.

왜 이 생각을 먼저 해야 하는지

삭제를 아무리 다르게 해도, 마지막 네 자리는 각각 특정한 $\mathrm{mod}5$ 위치에서 하나씩 온다는 구조가 변하지 않습니다.

단계별 풀이

1. 79장에서 5장씩 15번 지우면 정확히 4장이 남습니다.
2. 해설이 보여 주듯, 이 4장은 원래 위치가 각각 $1\mathrm{mod}5$, $2\mathrm{mod}5$, $3\mathrm{mod}5$, $4\mathrm{mod}5$인 카드들에서 하나씩 선택된다고 볼 수 있습니다.
3. 따라서 최종 네 자리 수를 최소화하려면, 첫 자리부터 사전순으로 가장 작게 만들어야 합니다.
4. 즉 첫 자리는 $1\mathrm{mod}5$ 위치 카드들 중 가능한 최솟값, 둘째 자리는 $2\mathrm{mod}5$ 위치 카드들 중 가능한 최솟값을 고르는 식으로 갑니다.
5. 해설의 최적 결과는 $5,4,7,6$입니다.
6. 따라서 만들 수 있는 가장 작은 네 자리 수는 $5476$입니다.

헷갈리기 쉬운 점

실제 삭제 순서를 하나하나 시뮬레이션하기보다, 마지막에 남는 자리의 나머지 구조를 먼저 보는 것이 중요합니다.

16. Plus Minus

문제 한눈에 보기

문자열의 모든 앞부분에서 + 개수가 - 개수보다 적어지지 않게 하려면, 어떤 -들을 최소 비용으로 +로 바꿔야 하는지 구하는 문제입니다.

답

최소 비용은 $39$입니다.

핵심 개념

처음으로 조건이 깨지는 위치에서는, 그 구간 안의 - 중 적어도 하나를 반드시 뒤집어야 합니다. 그래서 그중 가장 싼 것을 고르는 그리디가 최적입니다.

왜 이 생각을 먼저 해야 하는지

조건이 깨지는 순간 그 앞부분만 보면 되고, 그 순간에 필요한 수정은 최소 하나라는 사실이 핵심입니다.

단계별 풀이

1. +를 $+1$, -를 $-1$로 보고 앞에서부터 누적합 $P[i]-Q[i]$를 계산합니다.
2. 스캔하면서 지금까지 등장한 -들의 비용을 자료구조에 모아 둡니다.
3. 어떤 위치에서 처음으로 누적합이 음수가 되면, $1$번부터 그 위치까지의 - 중 하나는 반드시 +로 바뀌어야 합니다.
4. 그중 가장 싼 것을 바꾸는 것이 이후 어떤 선택과도 충돌하지 않는 최적 선택입니다.
5. 실제로는 가장 작은 비용을 꺼낼 수 있는 우선순위 큐를 쓰면 깔끔합니다.
6. 이 과정을 끝까지 반복하면 총 최소 비용이 $39$가 됩니다.

헷갈리기 쉬운 점

지금 막 만난 -를 바꾸는 것이 아니라, 지금까지 본 - 전체 중 가장 싼 것을 바꾸어야 합니다.

17. 식별 코드

문제 한눈에 보기

4비트 코드 8개를 골라서, 각 코드의 한 글자를 가린 뒤에도 원래 코드의 주인을 유일하게 알아낼 수 있게 만드는 문제입니다.

답

한 가지 정답은 다음 8개입니다.

$0000,0011,0101,0110,1001,1010,1100,1111$

핵심 개념

모든 짝수 패리티 4비트 코드를 쓰면 됩니다.

왜 이 생각을 먼저 해야 하는지

한 글자가 가려져도, 나머지 세 글자의 패리티를 보면 가려진 글자가 $0$인지 $1$인지 바로 복원할 수 있기 때문입니다.

단계별 풀이

1. 위 8개 코드는 모두 $1$의 개수가 짝수인 코드들입니다.
2. 이제 어떤 코드에서 한 자리를 가렸다고 합시다.
3. 남은 세 자리의 $1$ 개수를 세면, 전체를 짝수로 맞추기 위해 가려진 자리가 $0$이어야 하는지 $1$이어야 하는지 즉시 결정됩니다.
4. 따라서 가려진 뒤의 문자열을 보면 원래 코드가 정확히 하나로 복원됩니다.
5. 그래서 위 8개 코드는 문제의 조건을 만족합니다.

헷갈리기 쉬운 점

코드들이 서로 다르기만 해서는 부족합니다. 한 글자를 가린 뒤에도 서로 섞이지 않아야 합니다.

18. 낚시터

문제 한눈에 보기

시간과 위치가 주어진 물고기 등장 이벤트들 사이를 움직이며, 잡을 수 있는 물고기 수의 최댓값을 구하는 문제입니다.

답

최대로 잡을 수 있는 물고기 수는 $6$입니다.

핵심 개념

각 이벤트를 끝점으로 하는 동적 계획법을 세우면 됩니다.

왜 이 생각을 먼저 해야 하는지

한 이벤트에서 다음 이벤트로 갈 수 있는지는 시간 차이와 위치 차이만 보면 되므로, 전형적인 도달 가능성 DP로 바뀝니다.

단계별 풀이

1. 각 이벤트 $i$에 대해 위치를 $l_i$, 시간을 $t_i$라고 둡니다.
2. $f_i$를 “$i$번째 물고기를 마지막으로 잡았을 때까지 잡을 수 있는 물고기 수의 최댓값”이라고 정의합니다.
3. 어떤 이전 이벤트 $j$에서 $i$로 가려면 $|l_i-l_j|\le t_i-t_j$가 성립해야 합니다.
4. 따라서

$f_i=1+\max \{f_j:j<i\text{ 이고 }|l_i-l_j|\le t_i-t_j\}$

로 둘 수 있습니다. 5. 시작 위치는 시각 $0$에 자유롭게 정할 수 있으므로, 처음부터 잡을 수 있는 이벤트는 $f_i=1$이 됩니다. 6. 이 식으로 모든 $f_i$를 계산하면 최댓값이 $6$이 됩니다.

헷갈리기 쉬운 점

위아래 이동은 없고, 1차원 선분 위에서만 왼쪽, 오른쪽, 기다리기가 가능합니다.

19. 지폐 교환

문제 한눈에 보기

알파벳 A부터 I가 어떤 지폐를 뜻하는지 모를 때, 질문 두 번만으로 모든 대응을 유일하게 알아내는 문제입니다.

답

한 가지 정답은 $148450$원, $46740$원을 질문하는 것입니다.

핵심 개념

각 알파벳에 대해 (첫 번째 응답에서 나온 횟수, 두 번째 응답에서 나온 횟수)라는 횟수쌍을 만들면 됩니다.

왜 이 생각을 먼저 해야 하는지

질문 한 번만으로는 서로 같은 횟수로 나오는 지폐가 생길 수 있지만, 두 번의 결과를 묶으면 전부 다르게 만들 수 있습니다.

단계별 풀이

1. 먼저 $148450$을 최소 지폐 수로 나타내면
2. $50000\times 2,10000\times 4,5000\times 1,1000\times 3,100\times 4,50\times 1$입니다.
3. 다음 $46740$을 최소 지폐 수로 나타내면
4. $10000\times 4,5000\times 1,1000\times 1,500\times 1,100\times 2,10\times 4$입니다.
5. 따라서 각 액면가는 다음 횟수쌍을 가집니다.
6. 10원:(0,4), 50원:(1,0), 100원:(4,2), 500원:(0,1), 1000원:(3,1), 5000원:(1,1), 10000원:(4,4), 50000원:(2,0), 사용 안 된 알파벳:(0,0)입니다.
7. 이 9개의 쌍이 모두 서로 다르므로, 응답만 보면 어떤 알파벳이 어느 지폐인지 유일하게 복원할 수 있습니다.

헷갈리기 쉬운 점

핵심은 실제 알파벳 이름이 아니라 횟수쌍이 서로 모두 달라지는가입니다.

20. 사이클의 크기

문제 한눈에 보기

길이가 소수 N인 사이클 위에서, 다섯 번 이하의 코드 실행 결과만 보고 N을 알아내는 인터랙티브 문제입니다.

답

해설이 제시한 다섯 번의 명령을 쓰면 점프 횟수가 항상 $1,1,1000,x,y$가 되고,

$N=1000x+(y-1)$

로 복원할 수 있습니다. 그림 예시에서는 $x=981$, $y=62$이므로 $N=981061$입니다.

핵심 개념

N을 $1000$으로 나눈 몫과 나머지를 따로 읽어 내는 방식입니다.

왜 이 생각을 먼저 해야 하는지

N의 범위가 약 50만에서 100만 사이이므로, $1000$ 단위 블록과 나머지로 나누면 정보량을 매우 효율적으로 추출할 수 있습니다.

단계별 풀이

1. 해설의 초기 몇 번의 명령은 로봇이 특정 색 패턴을 만나도록 장치를 만드는 역할을 합니다.
2. 그 다음 큰 점프를 반복하는 명령으로 사이클 길이를 $1000$ 단위로 얼마나 넘는지 읽어 냅니다. 이것이 $x$입니다.
3. 마지막 명령은 남은 자투리 길이, 즉 나머지 부분을 읽어 내며 이것이 $y-1$에 해당합니다.
4. 따라서 전체 길이는 $1000$짜리 블록 $x$개와 남은 길이 $y-1$을 합친
5. $N=1000x+(y-1)$이 됩니다.
6. 예시 화면에서는 $x=981$, $y=62$이므로 $N=981000+61=981061$입니다.

헷갈리기 쉬운 점

마지막 값이 그대로 나머지가 아니라 나머지 + 1 꼴로 읽히므로 $y-1$을 써야 합니다.

개념 한눈에 보기

개념	나온 문제	기억할 말
제곱식 전개	1	$(\text{합}{)}^2$에서 서로 다른 두 수의 곱을 꺼낸다.
진법 변환	2	16진수와 8진수는 2진수를 거치면 안전하다.
크루스칼	3	가벼운 간선부터 넣고, 사이클이면 뺀다.
논리 퍼즐	4	자기 자신을 가리키는 문장부터 본다.
명제식 정리	5	함축을 없애고 동치식으로 줄인다.
Lehmer code	6	뒤에서 c_i+1번째로 큰 수를 고른다.
함수 그래프	7	긴 이동은 결국 사이클 길이의 나머지다.
비트 분리	8	비트별 기여를 따로 세면 된다.
힙 라벨링	9	서브트리별로 값 집합을 나누어 센다.
선형 결합	10	낸 돈과 거스름돈을 함께 식에 넣는다.
상태 그래프	11	정점만이 아니라 방문 홀짝까지 상태다.
생성함수	12	계수를 작은 차수부터 비교해 복원한다.
행 우선 그리디	13	앞칸을 지나기 전에 필요한 처리를 끝낸다.
교환 논법	14	가장 앞 카드가 미래 선택지를 가장 덜 망친다.
나머지 클래스	15	마지막 카드의 원래 위치는 $\mathrm{mod}5$로 묶인다.
최소 비용 수정	16	처음 깨지는 접두사에서 가장 싼 -를 바꾼다.
패리티 코드	17	짝수 패리티면 한 비트를 가려도 복원된다.
도달 가능 DP	18	`
횟수쌍 설계	19	두 응답의 등장 횟수쌍이 모두 달라야 한다.
몫과 나머지	20	$1000x+(y-1)$ 형태로 사이클 길이를 읽는다.