1 - 2022 KOI 1교시 초등부 풀이 정리

2022 KOI 1교시 초등부 풀이 정리

이 문서는 2022 - 초등부 기출문제를 바탕으로, 정답 자료를 초등학생도 따라가기 쉽게 학습용 풀이로 다시 쓴 문서입니다. 2022 초등부 자료는 정답 중심 PDF이므로, 문제와 정답을 바탕으로 풀이 이유를 다시 구성했습니다.

1. Lyndon word

문제 한눈에 보기

foobar에서 맨 앞 글자를 맨 뒤로 보내는 회전을 반복할 때, 사전에서 가장 앞서는 문자열이 몇 번 이동 뒤에 나오는지 묻는 문제입니다.

답

$4$

핵심 개념

회전해서 나오는 문자열들을 직접 적고, 사전 순으로 가장 빠른 것을 찾으면 됩니다.

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

문자열 길이가 6이라 경우가 많지 않습니다. 괜히 규칙을 찾기보다 전부 적는 것이 가장 빠릅니다.

단계별 풀이

1. 가능한 문자열은 foobar, oobarf, obarfo, barfoo, arfoob, rfooba입니다.
2. 첫 글자만 봐도 $a$로 시작하는 arfoob가 가장 앞섭니다.
3. arfoob는 foobar에서 처음 4글자 foob를 뒤로 보냈을 때 얻습니다.
4. 따라서 정답은 $4$입니다.

헷갈리기 쉬운 점

원래 문자열도 하나의 후보입니다. 문제는 “몇 개의 문자를 뒤로 옮겼을 때”이므로 회전 횟수를 세야 합니다.

2. 케이크 도난 사건

문제 한눈에 보기

P 또는 R은 먹었다, P를 안 먹었거나 Q가 먹었다라는 두 조건에서 반드시 참인 문장을 찾는 문제입니다.

답

Q, R 중 적어도 한 명은 반드시 케이크를 먹었다.

핵심 개념

한 사람을 기준으로 경우를 둘로 나누면 됩니다.

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

논리 문제는 식을 길게 쓰는 것보다 “Q가 먹었는가, 안 먹었는가”처럼 갈라 보면 금방 정리됩니다.

단계별 풀이

1. 만약 Q가 케이크를 먹었다면, 이미 Q 또는 R이 참입니다.
2. 만약 Q가 먹지 않았다면, 두 번째 조건 P를 안 먹었거나 Q가 먹었다에서 Q 부분은 거짓이므로 P를 안 먹었다가 반드시 참입니다.
3. 그러면 첫 번째 조건 P 또는 R에서 P는 거짓이므로 R이 반드시 참이어야 합니다.
4. 어느 경우든 Q, R 중 적어도 한 명은 먹었다가 됩니다.

헷갈리기 쉬운 점

P를 안 먹었거나 Q가 먹었다는 둘 중 하나만 참이어도 되는 문장입니다.

3. 유람선

문제 한눈에 보기

모자를 떨어뜨린 뒤 10분 동안 배는 서쪽으로 더 가고, 그 뒤 동쪽으로 돌아옵니다. 몇 분 뒤 모자를 다시 만나는지 구하는 문제입니다.

답

$10$분

핵심 개념

배와 모자의 상대속도를 보면 됩니다.

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

강물은 배와 모자 둘 다 함께 움직이므로, “둘 사이 거리”만 보면 계산이 아주 쉬워집니다.

단계별 풀이

1. 모자는 물과 함께 서쪽으로 시속 $2$km로 움직입니다.
2. 배는 서쪽으로 갈 때 시속 $12$km이므로, 모자와의 거리는 시속 $10$km씩 벌어집니다.
3. 10분은 $1/6$시간이므로, 반환점에서 둘 사이 거리는 $10\times 1/6=5/3\mathrm{km}$입니다.
4. 이제 배는 동쪽으로 시속 $8$km, 모자는 서쪽으로 시속 $2$km이므로 서로 시속 $10$km로 가까워집니다.
5. $5/3\mathrm{km}$를 시속 $10$km로 줄이는 데 걸리는 시간은 $1/6$시간, 즉 $10$분입니다.

헷갈리기 쉬운 점

돌아올 때는 $8-2$가 아니라 서로 반대 방향이므로 $8+2$로 계산해야 합니다.

4. 그래프 만들기

문제 한눈에 보기

6개 정점의 차수가 주어진 대로 되는 그래프를 실제로 만들 수 있는 보기 하나를 찾는 문제입니다.

답

$4,2,4,2,3,3$

핵심 개념

차수 수열은 Havel-Hakimi처럼 줄여 보면서 가능한지 판단할 수 있습니다.

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

겉보기로는 그럴듯해 보여도 실제 그래프가 안 되는 경우가 많아서, 숫자를 줄여 보는 검사가 가장 확실합니다.

단계별 풀이

1. 정답 보기를 큰 수부터 쓰면 $4,4,3,3,2,2$입니다.
2. 앞의 $4$를 빼고 나머지 네 수를 1씩 줄이면 $3,2,2,2,1$이 됩니다.
3. 다시 $3$을 빼고 세 수를 줄이면 $1,1,1,1$이 됩니다.
4. 그다음 $1,1,0$, 마지막에 $0,0$까지 가므로 가능한 수열입니다.
5. 다른 보기들은 홀수 합이 나오거나, 줄이다 보면 음수가 생겨 만들 수 없습니다.

헷갈리기 쉬운 점

차수의 총합은 항상 짝수여야 합니다. 이것만으로도 몇몇 보기는 바로 탈락합니다.

5. 경진대회

문제 한눈에 보기

상의 등급 인원이 $k,k+1,k+2,\cdots$처럼 늘어날 때, (9등, 2등급), (17등, 3등급), (27등, 4등급)를 만족하는 $k$의 최소와 최대를 구하는 문제입니다.

답

최소 6, 최대 7

핵심 개념

각 등급 구간의 시작과 끝을 식으로 써서 $k$의 범위를 좁히면 됩니다.

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

등급은 “몇 번째부터 몇 번째까지”가 중요합니다. 구간으로 쓰면 세 조건을 바로 겹칠 수 있습니다.

단계별 풀이

1. 2등급은 $k+1$등부터 $2k+1$등까지입니다.
2. 9등이 2등급이므로 $k+1\le 9\le 2k+1$이고, 여기서 $4\le k\le 8$이 나옵니다.
3. 3등급은 $2k+2$등부터 $3k+3$등까지입니다.
4. 17등이 3등급이므로 $2k+2\le 17\le 3k+3$이고, 여기서 $5\le k\le 7$입니다.
5. 4등급은 $3k+4$등부터 $4k+6$등까지입니다.
6. 27등이 4등급이므로 $3k+4\le 27\le 4k+6$이고, 여기서 $6\le k\le 7$입니다.
7. 세 범위를 모두 겹치면 $k=6,7$만 남습니다.

헷갈리기 쉬운 점

3등급의 시작은 $2k+1$이 아니라 그다음 등수인 $2k+2$입니다.

6. 달리기

문제 한눈에 보기

다섯 사람의 순위 조건을 보고 3등이 누구인지 찾는 문제입니다.

답

A

핵심 개념

등수의 위아래 관계만으로도 자리를 꽤 많이 고정할 수 있습니다.

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

한 사람씩 완전히 배열하려고 하면 복잡합니다. 먼저 “반드시 맨 끝”, “반드시 위”, “반드시 아래”를 찾는 것이 좋습니다.

단계별 풀이

1. B보다 순위가 낮은 사람은 없다는 말은 B가 가장 낮은 등수, 즉 $5$등이라는 뜻입니다.
2. E의 순위는 B와 A 사이이므로, E는 A보다 낮고 B보다는 높습니다.
3. 또 A는 C보다 낮고, D는 A보다 높습니다.
4. 따라서 A보다 위에는 최소한 C와 D 두 명이 있습니다.
5. A보다 아래에는 E와 B가 있습니다.
6. 위에 두 명, 아래에 두 명이 있으니 A는 정확히 $3$등입니다.

헷갈리기 쉬운 점

이 문제에서 “순위가 낮다”는 더 못한 등수, 즉 숫자가 더 큰 쪽입니다.

7. 두 트리 연결하기

문제 한눈에 보기

왼쪽 트리와 오른쪽 트리를 길이 0인 간선 하나로 이어서, A에서 B까지 가는 길이가 5가 되게 하는 연결을 찾는 문제입니다.

답

나-다

핵심 개념

연결한 뒤의 전체 거리는 A에서 왼쪽 연결점까지 거리 + B에서 오른쪽 연결점까지 거리입니다.

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

새 간선의 길이가 0이므로, 실제로는 양쪽에서 연결점까지 몇 칸인지 세는 문제로 바뀝니다.

단계별 풀이

1. 각 보기마다 왼쪽 연결점까지의 거리와 오른쪽 연결점에서 B까지의 거리를 셉니다.
2. 그 두 값을 더하면 새로 연결한 뒤의 A-B 거리입니다.
3. 그림을 기준으로 세어 보면 합이 정확히 $5$가 되는 경우는 나-다뿐입니다.
4. 따라서 정답은 나-다입니다.

헷갈리기 쉬운 점

새 간선은 길이 $1$이 아니라 $0$입니다. 그래서 가운데 연결 비용을 더하면 안 됩니다.

8. 통로 위의 강아지

문제 한눈에 보기

여섯 마리 강아지에게 목줄을 연결할 때, 목줄 길이 합이 최소가 되는 위치가 아닌 것을 찾는 문제입니다.

답

$3$

핵심 개념

격자 통로에서 최단 거리는 가로 차이와 세로 차이를 더한 맨해튼 거리입니다.

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

직선거리처럼 보지 말고 통로를 따라 몇 칸 가야 하는지로 봐야, 합이 가장 작은 위치를 찾을 수 있습니다.

단계별 풀이

1. 각 후보 $1,2,3,4,5$에서 여섯 강아지까지의 통로 거리 합을 비교합니다.
2. 이런 종류의 문제는 가로 좌표의 가운데, 세로 좌표의 가운데 쪽이 유리합니다.
3. 그림에서 $1,2,4,5$는 그 가운데 영역에 놓여 있어 거리 합이 최소입니다.
4. $3$은 그 영역에서 벗어나 있어서 전체 거리 합이 더 커집니다.
5. 따라서 옳지 않은 위치는 $3$입니다.

헷갈리기 쉬운 점

대각선으로 곧장 가는 거리가 아닙니다. 통로를 따라 꺾어 가는 길이를 세야 합니다.

9. 나이

문제 한눈에 보기

세 아이 나이의 곱이 72이고, 합을 들어도 아직 못 맞히다가 “제일 큰 아이가 한 명”이라는 말을 듣고 맞히는 상황입니다. 처음 합이 얼마였는지 구하는 문제입니다.

답

$14$

핵심 개념

곱이 같은 나이 조합들을 적고, 합이 같은 경우를 찾으면 됩니다.

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

합을 듣고도 못 맞혔다는 말은 같은 합을 갖는 후보가 둘 이상 있다는 뜻입니다.

단계별 풀이

1. 곱이 $72$가 되는 나이 조합을 적어 보면 $(2,6,6)$과 $(3,3,8)$이 둘 다 합 $14$를 만듭니다.
2. 그래서 합이 $14$라면 아직 어느 조합인지 바로 못 맞힙니다.
3. 그런데 “제일 큰 아이가 한 명”이라는 말이 추가되면 $(2,6,6)$은 탈락합니다. 가장 큰 나이 $6$이 두 명이기 때문입니다.
4. 그러면 $(3,3,8)$만 남습니다.
5. 따라서 선생님이 처음 말해 준 합은 $14$입니다.

헷갈리기 쉬운 점

합이 애매한 경우가 하나만 있어야 합니다. 그래야 마지막 힌트로 딱 하나로 정해집니다.

10. 점프

문제 한눈에 보기

정확히 6번 움직일 때 도착할 수 있는 위치들 중에서 $19$와 가장 가까운 것을 찾는 문제입니다.

답

$18$

핵심 개념

한 번 기본 이동을 하고 나서 점프만 이어 가면 $1,3,7,15,\cdots =2^t-1$ 꼴이 됩니다.

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

점프는 바로 전 거리의 2배라서, 이동을 몇 덩어리로 끊었는지가 중요합니다.

단계별 풀이

1. 6번 이동은 $1+1+1+1+1+1$, $2+1+1+1+1$, $2+2+1+1$, $3+1+1+1$, $4+2$ 같은 덩어리로 생각할 수 있습니다.
2. 길이 $t$인 한 덩어리의 이동 거리는 $2^t-1$입니다.
3. 그래서 가능한 도착 위치는 $6,7,8,9,10,11,14,17,18,32,63$입니다.
4. 이 중 $19$와 가장 가까운 값은 $18$입니다.

헷갈리기 쉬운 점

점프만 따로 시작할 수는 없습니다. 첫 이동은 반드시 기본 이동 1입니다.

11. 블록 쌓기

문제 한눈에 보기

세 블록을 회전해 가며 가장 높게 쌓을 때 높이의 최댓값을 구하는 문제입니다.

답

$16$

핵심 개념

각 블록에서 “밑면 두 변”과 “높이”를 어떻게 정할지 따져 보면 됩니다.

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

블록은 회전할 수 있으므로, 숫자 세 개 중 어느 것을 높이로 세울지가 핵심입니다.

단계별 풀이

1. $(4,4,9)$ 블록은 높이를 $4$로 두고 밑면을 $9\times 4$로 만들 수 있습니다.
2. 그 위에 $(2,5,8)$ 블록을 높이 $8$, 밑면 $5\times 2$로 놓을 수 있습니다.
3. 마지막으로 $(3,2,4)$ 블록을 높이 $4$, 밑면 $3\times 2$로 올릴 수 있습니다.
4. 밑면 조건 $9\times 4\ge 5\times 2\ge 3\times 2$가 모두 맞습니다.
5. 전체 높이는 $4+8+4=16$입니다.

헷갈리기 쉬운 점

가장 큰 수를 무조건 높이로 세우는 것이 항상 정답은 아닙니다. 아래 블록은 넓은 밑면이 더 중요할 수 있습니다.

12. 초콜릿

문제 한눈에 보기

14칸 초콜릿을 2칸 묶음과 3칸 묶음으로 자르되, 각 묶음에 불량품이 2개 이상 들어가면 안 됩니다. 가장 비싸게 파는 방법을 찾는 문제입니다.

답

$25$

핵심 개념

왼쪽부터 잘라 가며 2칸으로 자를지, 3칸으로 자를지를 비교하는 동적 계획법 문제입니다.

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

한 번 자른 뒤에는 다시 붙일 수 없으므로, 앞부분을 어떻게 자르느냐가 뒤 선택에도 영향을 줍니다.

단계별 풀이

1. 그림의 불량품 위치를 표시해 둡니다.
2. 연속한 $2$칸 또는 $3$칸이 조건을 만족하면 그 묶음 가격을 붙입니다.
3. 앞에서부터 “지금까지 얻을 수 있는 최대 금액”을 차례로 계산합니다.
4. 그림의 배치에서는 어떤 구간은 3칸 묶음이 유리하고, 어떤 구간은 2칸 묶음이 더 유리합니다.
5. 이렇게 끝까지 비교하면 최댓값이 $25$달러가 됩니다.

헷갈리기 쉬운 점

3칸 묶음 7달러가 가장 비싸 보이지만, 불량품 위치 때문에 항상 3칸씩 자를 수 있는 것은 아닙니다.

13. 게임

문제 한눈에 보기

여섯 사람이 가진 1원짜리 동전을 써서 두 명씩 게임을 할 때, 총 게임 수를 최대화하는 문제입니다.

답

$17$번

핵심 개념

한 게임은 동전 2개를 씁니다. 그래서 전체 동전 수의 절반이 절대 상한입니다.

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

아무리 잘 짜도 한 게임마다 동전 2개는 반드시 사라집니다. 먼저 최대 가능 횟수부터 잡아야 합니다.

단계별 풀이

1. 그림의 동전 수를 모두 더하면 총 $34$개입니다.
2. 따라서 게임 수는 아무리 많아도 $34÷2=17$번을 넘을 수 없습니다.
3. 정답 자료의 한 가지 방법은 다음과 같습니다.
4. A-B 세 번, A-F 두 번, B-C 세 번, C-E 한 번, C-F 여섯 번, D-E 두 번입니다.
5. 이 방법으로 정확히 $17$번 게임할 수 있으므로, 최대값은 $17$입니다.

헷갈리기 쉬운 점

상한을 찾았다고 끝이 아닙니다. 그 상한이 실제로 가능한지도 꼭 보여야 합니다.

14. 생산

문제 한눈에 보기

$2\times 13$ 격자에서 사용할 수 있는 칸들끼리만 짝지어 부품을 최대한 많이 만드는 문제입니다.

답

최대 $7$개

핵심 개념

이 문제는 “서로 겹치지 않게 인접한 두 칸을 짝짓는” 최대 매칭 문제로 볼 수 있습니다.

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

한 칸은 한 번만 쓸 수 있으니, 좋은 짝을 먼저 잡다가 다른 짝을 막을 수도 있습니다. 전체 그림으로 봐야 합니다.

단계별 풀이

1. 가능한 칸들을 가로 또는 세로로 이어 보며 서로 겹치지 않는 짝을 만듭니다.
2. 정답 자료의 배치처럼 짝을 잡으면 총 $7$개의 부품을 만들 수 있습니다.
3. 남는 칸들의 모양을 보면 여덟 번째 부품까지 만들 만큼 독립된 빈 칸 쌍이 남지 않습니다.
4. 따라서 최대 생산 개수는 $7$입니다.

헷갈리기 쉬운 점

눈앞의 세로 짝 하나를 만들면, 뒤에서 가로 두 짝을 놓칠 수 있습니다. 그래서 “지금 보이는 한 쌍”만 고르면 안 됩니다.

15. 짝

문제 한눈에 보기

문자 몇 개를 지워서 남은 문자열이 AA, BB, CC의 이어붙이기가 되도록 만들 때, 지워야 하는 최소 문자 수를 구하는 문제입니다.

답

$9$개

핵심 개념

남길 문자열은 인접한 두 글자씩 같은 문자로 끊겨야 합니다.

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

이 문제는 “무엇을 지울까”보다 “어떤 짝들을 남길까”로 보는 편이 훨씬 쉽습니다.

단계별 풀이

1. 남는 문자열은 $(AA)(BB)(CC)\cdots$처럼 두 글자씩 같은 묶음으로 나뉘어야 합니다.
2. 따라서 원래 문자열에서 그런 짝들을 가장 많이 남기는 것이 목표입니다.
3. 정답 그림처럼 $9$개를 제거하면 남은 문자열을 같은 글자 두 개씩의 묶음으로 만들 수 있습니다.
4. 정답 자료에서는 이것이 최소 제거 횟수임을 보였고, 같은 개수의 다른 정답도 인정됩니다.

헷갈리기 쉬운 점

같은 글자가 짝수 개 있다고 해서 끝이 아닙니다. 남은 문자열에서 서로 붙어 있어야 AA, BB, CC 꼴이 됩니다.

16. 지뢰찾기

문제 한눈에 보기

원형으로 놓인 칸들에서, 각 칸의 숫자가 “양옆 두 칸 중 지뢰 개수”를 뜻할 때 지뢰 위치를 찾아내는 문제입니다.

답

정답 그림에 표시된 배치 중 아무거나

핵심 개념

지뢰 여부를 $0$과 $1$로 두면, 각 숫자는 이웃한 두 칸의 합이 됩니다.

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

원형이라 복잡해 보여도, 첫 칸을 하나 정하면 나머지를 차례대로 밀어 가며 결정할 수 있습니다.

단계별 풀이

1. 각 칸의 지뢰 여부를 $m[i]$라고 두면, 주어진 숫자는 $m[i-1]+m[i+1]$가 됩니다.
2. 원형이므로 맨 앞의 값을 한 번 가정하면 그다음 칸들 값이 차례로 정해집니다.
3. 마지막에 처음 칸과의 조건까지 맞는지 확인하면 가능한 배치를 찾을 수 있습니다.
4. PDF에는 3개의 상황에 대한 한 가지 정답 배치가 그림으로 제시되어 있고, 그 배치대로 두면 정답입니다.

헷갈리기 쉬운 점

이 문제는 가능한 배치가 여러 개일 수 있습니다. 하나만 맞게 찾으면 됩니다.

17. 수열 만들기

문제 한눈에 보기

전부 0인 수열 B에 구간 덧셈을 반복해 목표 수열 A를 만들 때, 작업 수를 최소로 하는 문제입니다.

답

10번 작업

핵심 개념

수열의 높이를 여러 개의 가로 띠로 나누어 덧칠한다고 생각하면 됩니다.

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

한 번의 작업은 한 구간 전체를 같은 높이만큼 올리는 일이라서, 그림으로 보면 “직사각형 한 장을 더하는 것”과 같습니다.

단계별 풀이

1. 정답 자료의 한 가지 방법은 다음 순서입니다.
2. $[1,12]$에 $1$, $[1,3]$에 $2$, $[8,12]$에 $7$, $[10,12]$에 $2$, $[5,6]$에 $2$
3. 이어서 $[1,1]$에 $2$, $[3,3]$에 $3$, $[6,6]$에 $3$, $[8,8]$에 $7$, $[11,11]$에 $2$를 더합니다.
4. 이렇게 하면 정확히 10번 만에 $B=A$가 됩니다.
5. 정답 자료에서는 10번이 최소이며, 다른 10번짜리 방법도 정답으로 인정합니다.

헷갈리기 쉬운 점

큰 수를 한 번에 많이 더하는 것이 항상 좋은 건 아닙니다. 나중에 필요한 모양까지 함께 맞아야 합니다.

18. 아이템 만들기

문제 한눈에 보기

나뭇잎, 돌, 나뭇가지를 모아 거래를 해서 은 7개를 만든 뒤 검 1개를 얻을 때, 코인을 최소로 쓰는 방법을 찾는 문제입니다.

답

$28$코인

핵심 개념

은 7개를 가장 싸게 만드는 거래 조합을 먼저 찾아야 합니다.

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

검은 마지막에 은 7개만 있으면 되므로, 앞부분은 결국 “은을 제일 싸게 만드는 법” 문제입니다.

단계별 풀이

1. 거래 1은 돌 2 + 나뭇잎 1로 은 1개를 만드는데 비용이 $5$코인입니다.
2. 거래 2는 돌 1 + 나뭇가지 2로 은 2개, 거래 3은 돌 3 + 나뭇가지 2로 은 3개를 만듭니다.
3. 은 7개를 만들면서 거래 1을 쓰면 너무 비싸므로, 거래 2와 거래 3 위주로 보는 것이 유리합니다.
4. 거래 2 두 번 + 거래 3 한 번이면 은이 $2+2+3=7$개가 됩니다.
5. 필요한 재료는 돌 $5$개, 나뭇가지 $6$개이고, 비용은 $5\times 2+6\times 3=28$코인입니다.
6. 실제 제작 순서는 나뭇가지 6개와 돌 5개를 모은 뒤 거래 2, 거래 2, 거래 3, 거래 4를 하면 됩니다.

헷갈리기 쉬운 점

은 1개짜리 거래가 있어 보여도, “한 개만 보고 싸다”가 아니라 최종 은 7개 전체 비용을 봐야 합니다.

19. 트리 순회

문제 한눈에 보기

트리에서 시작점을 정하고 간선을 최대 18번 따라가며, 서로 다른 정점을 최대한 많이 방문하는 문제입니다.

답

14개 정점을 방문하는 방법이 정답

핵심 개념

트리에서는 새로운 가지로 들어갈 때마다 다시 돌아오는 비용도 함께 생각해야 합니다.

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

한쪽 끝만 멀리 갔다 오면 이동 수를 많이 써 버립니다. 그래서 “되돌아오는 값까지 포함한 이득”이 큰 가지를 골라야 합니다.

단계별 풀이

1. 정답 자료의 한 가지 방문 순서는
2. $4\to 3\to 2\to 5\to 6\to 7\to 6\to 5\to 8\to 9\to 8\to 11\to 15\to 11\to 8\to 17\to 22\to 24\to 25$
3. 이 순서로 가면 총 18번 이동 안에서 서로 다른 정점 14개를 방문할 수 있습니다.
4. 핵심은 중간 갈림점으로 되돌아와서, 한 번의 복귀로 다음 큰 가지까지 이어 가는 것입니다.

헷갈리기 쉬운 점

같은 정점을 다시 지나갈 수는 있지만, 방문 수는 한 번만 셉니다.

20. 카드 가져가기

문제 한눈에 보기

양 끝 카드만 가져갈 수 있을 때, 점수 계수 $[1,2,-3,3,-2,1]$를 고려해 총점을 최대로 하는 순서를 찾는 문제입니다.

답

오른쪽, 오른쪽, 왼쪽, 오른쪽, 오른쪽, 왼쪽

핵심 개념

양수 계수에는 큰 카드를, 음수 계수에는 작은 카드를 맞추는 것이 유리합니다.

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

가져가는 순서는 6번뿐이지만, 앞 선택이 뒤 선택 가능성을 바꿉니다. 그래서 “좋은 카드와 좋은 계수의 맞춤”을 봐야 합니다.

단계별 풀이

1. 3번째와 5번째 계수는 음수이므로, 그 자리에 너무 큰 수가 오면 손해입니다.
2. 반대로 2번째와 4번째 계수는 양수이므로 큰 수를 배치하고 싶습니다.
3. 정답 자료의 최적 순서는 오른쪽, 오른쪽, 왼쪽, 오른쪽, 오른쪽, 왼쪽입니다.
4. 이 순서를 따르면 큰 수들은 양수 계수와 만나고, 불리한 카드는 음수 계수 쪽으로 밀려 총점이 최대가 됩니다.

헷갈리기 쉬운 점

지금 당장 큰 카드를 고르는 것이 항상 최선은 아닙니다. 다음 계수가 음수라면 일부러 작은 카드를 남겨 두는 편이 좋을 수 있습니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
사전순 비교	1	가능한 회전 문자열을 직접 적어 가장 앞선 것을 고른다.
논리와 경우 나누기	2, 6, 9	참거짓과 순위 조건을 둘로 나누면 답이 정해진다.
상대속도	3	강물 자체보다 배와 모자의 거리 변화만 본다.
그래프/트리 구조	4, 7, 19	차수, 거리, 되돌아오는 비용을 함께 생각한다.
구간 세기	5	등급별 시작 등수와 끝 등수를 식으로 쓴다.
맨해튼 거리	8	격자 통로에서는 가로 차이와 세로 차이의 합이 거리다.
점화식/가능한 상태	10, 12	가능한 이동값이나 최댓값을 앞에서부터 쌓아 간다.
회전과 배치	11, 14, 15	밑면 조건이나 짝짓기 조건을 만족하도록 모양을 맞춘다.
최적화	13, 18, 20	전체 자원 상한과 이득이 큰 선택을 함께 본다.
구성형 정답	16, 17	조건을 만족하는 한 가지 올바른 배치를 만들면 된다.