2 - 2025 KOI 1교시 중등부 풀이 정리

2025 KOI 1교시 중등부 풀이 정리

이 문서는 2025 - 중등부 기출문제를 바탕으로, 중학생 기준에서 읽기 쉽게 다시 정리한 학습용 풀이 노트입니다. 공식 해설의 핵심 아이디어는 살리고, 설명은 더 짧고 분명하게 바꾸었습니다.

1. 제곱수 연도

문제 한눈에 보기

2025년 다음에 오는 제곱수 연도들 중, 두 번째로 가까운 해가 몇 년 뒤인지 구하는 문제입니다.

답

$184$

핵심 개념

2025는 45²이므로 다음 제곱수는 46², 47² 순서로 찾으면 됩니다.

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

제곱수는 바로 다음 자연수의 제곱으로 이어지므로 멀리 볼 필요가 없습니다.

단계별 풀이

1. $2025=45^2$입니다.
2. 올해 이후 가장 가까운 제곱수 연도는 $46^2=2116$입니다.
3. 두 번째로 가까운 제곱수 연도는 $47^2=2209$입니다.
4. 따라서 물어보는 값은 $2209-2025=184$입니다.

헷갈리기 쉬운 점

“올해 이후”이므로 2025년은 세지 않습니다.

2. 스택

문제 한눈에 보기

주어진 push, pop 연산을 그대로 따라가서 보기 중 틀린 문장을 찾는 문제입니다.

답

옳지 않은 것은 스택에서 마지막에서 세 번째로 빠져나온 자연수는 6이다.입니다.

핵심 개념

스택은 LIFO, 즉 나중에 넣은 것이 먼저 나오는 구조입니다.

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

한 번이라도 pop 순서를 잘못 적으면 이후 판단이 전부 틀어집니다.

단계별 풀이

1. $1,2,3,4$를 넣고 2개를 빼면 $4,3$이 나옵니다.
2. $5,6,7,8,9$를 넣고 3개를 빼면 $9,8,7$이 나옵니다.
3. $10,11$을 넣고 남은 것을 다 빼면 $11,10,6,5,2,1$이 나옵니다.
4. 따라서 전체 pop 순서는 $4,3,9,8,7,11,10,6,5,2,1$입니다.
5. 마지막에서 세 번째는 $6$이 아니라 $5$입니다.

헷갈리기 쉬운 점

“마지막에서 세 번째”는 뒤에서 세는 말입니다.

3. 산의 높이

문제 한눈에 보기

산들 사이의 높이 관계를 식으로 정리해서 $x+y$를 구하는 문제입니다.

답

$50$

핵심 개념

한 산을 기준으로 다른 산들의 높이를 모두 표현하면 차이가 바로 나옵니다.

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

문장을 따로따로 읽기보다 기준을 하나 정해서 식으로 적는 것이 훨씬 깔끔합니다.

단계별 풀이

1. $C=c$라고 두겠습니다.
2. B는 C보다 $50$ 낮으므로 $B=c-50$입니다.
3. A는 B보다 $30$ 높으므로 $A=c-20$입니다.
4. E는 A보다 $10$ 높으므로 $E=c-10$입니다.
5. F는 C보다 $20$ 높으므로 $F=c+20$입니다.
6. 따라서 $x=|C-E|=10$, $y=|A-F|=40$입니다.
7. 그래서 $x+y=50$입니다.

헷갈리기 쉬운 점

높이 차이는 절댓값입니다. 어느 쪽이 더 높은지만 바뀌고 차이는 같습니다.

4. 달리기 시합

문제 한눈에 보기

각 로봇의 남은 거리를 이용해 속력 비를 찾고, A가 도착한 순간 D가 얼마나 남았는지 구하는 문제입니다.

답

$36$

핵심 개념

같은 시간 동안 달린 거리의 비는 속력의 비와 같습니다.

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

문장에 반복해서 나오는 “누가 도착했을 때 다른 로봇이 얼마 남았는가”는 속력 비교를 하라는 뜻입니다.

단계별 풀이

1. A가 50m를 달렸을 때 B는 40m를 달렸으므로 $v_B=4/5v_A$입니다.
2. B가 50m를 달렸을 때 C는 35m를 달렸으므로 $v_C=35/50v_B=7/10v_B$입니다.
3. C가 50m를 달렸을 때 D는 25m를 달렸으므로 $v_D=1/2v_C$입니다.
4. 따라서

$v_D=v_A\times 4/5\times 7/10\times 1/2=7/25v_A$

5. A가 결승선을 통과하는 순간 D는 $50\times 7/25=14\mathrm{m}$를 달린 상태입니다.
6. 남은 거리는 $50-14=36\mathrm{m}$입니다.

헷갈리기 쉬운 점

남은 거리에서 바로 비를 잡지 말고, 먼저 달린 거리로 바꾸어야 합니다.

5. 마법 문자열

문제 한눈에 보기

최종 문자열이 주어졌을 때, 어떤 주문을 어떤 순서로 외쳤는지 복원하는 문제입니다.

답

$12122211221$

핵심 개념

정방향보다 역방향 복원이 훨씬 쉽습니다.

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

$2$ 주문은 문자열 전체를 뒤집기 때문에, 처음부터 따라가면 중간 상태가 복잡해집니다.

단계별 풀이

1. 마지막 글자가 $1$이면 마지막 주문은 $1$이므로 맨 뒤 $1$을 지웁니다.
2. 마지막 글자가 $2$이면 마지막 주문은 $2$이므로, 맨 뒤 $2$를 지우고 남은 문자열을 뒤집습니다.
3. $221211221121$에 이 과정을 반복하면
4. $221211221121\to 22121122112\to 1122112122\to 212112211\to \cdots \to 1$
5. 이렇게 얻은 주문은 뒤에서부터 찾은 것이므로, 마지막에 순서를 뒤집습니다.
6. 그래서 정답은 $12122211221$입니다.

헷갈리기 쉬운 점

거꾸로 찾은 순서를 그대로 쓰면 안 되고, 마지막에 뒤집어야 합니다.

6. 숫자 제거

문제 한눈에 보기

길이 9인 수에서 5개를 지워 만들 수 있는 모든 4자리 수를 큰 순서로 정렬했을 때, 49번째를 구하는 문제입니다.

답

$5673$

핵심 개념

큰 수 순서는 앞자리부터 결정되므로, 첫째 자리를 기준으로 경우를 나누면 됩니다.

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

4자리 수의 크기는 첫째 자리, 둘째 자리, 셋째 자리 순으로 결정됩니다.

단계별 풀이

1. 첫 자리가 $9$인 경우는, $9$ 뒤의 7개 숫자 중 3개를 고르는 경우라서 $C(7,3)=35$개입니다.
2. 첫 자리가 $8$인 경우는 $8734$ 하나뿐입니다.
3. 첫 자리가 $6$인 경우는 $4$개입니다.
4. 따라서 여기까지 합치면 $35+1+4=40$개입니다.
5. 그러므로 49번째는 $5$로 시작하는 수들 중 9번째입니다.
6. $5$ 뒤에서 만들 수 있는 3자리 수를 큰 순서대로 적으면
7. $874,873,834,734,687,684,683,674,673,634$입니다.
8. 이 중 9번째가 $673$이므로 정답은 $5673$입니다.

헷갈리기 쉬운 점

원래 숫자의 상대적인 순서는 바꿀 수 없습니다.

7. 나머지 만들기

문제 한눈에 보기

세 개의 나눗셈 조건을 동시에 만족하는 모든 $n$의 합을 구하는 문제입니다.

답

$50$

핵심 개념

나머지 조건은 “차이가 $n$의 배수”라는 말로 바꿀 수 있습니다.

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

나머지 문제는 최대공약수 문제로 바꾸는 순간 구조가 단순해집니다.

단계별 풀이

1. $341\equiv 5(\mathrm{mod}n)$이면 $336$은 $n$의 배수입니다.
2. 마찬가지로 $504$, $576$도 $n$의 배수입니다.
3. 따라서 $n$은 $\gcd (336,504,576)$의 약수입니다.
4. 계산하면 최대공약수는 $24$입니다.
5. 또 나머지가 $5$이므로 $n>5$여야 합니다.
6. $24$의 약수 중 $5$보다 큰 것은 $6,8,12,24$입니다.
7. 합은 $50$입니다.

헷갈리기 쉬운 점

나누는 수는 항상 나머지보다 커야 합니다.

8. 19 단의 자릿수

문제 한눈에 보기

19단표 전체에 적힌 수들의 자릿수 합을 구하는 문제입니다.

답

$845$

핵심 개념

한 자리 수, 두 자리 수, 세 자리 수 개수를 나누어 세면 됩니다.

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

$A+2B+3C$는 바로 전체 자릿수 합입니다.

단계별 풀이

1. 전체 칸 수는 $19\times 19=361$칸입니다.
2. 한 자리 수는 곱이 $9$ 이하인 칸이고, 세어 보면 $23$개입니다.
3. 세 자리 수는 곱이 $100$ 이상인 칸이고, 세어 보면 $146$개입니다.
4. 두 자리 수는 나머지이므로 $361-23-146=192$개입니다.
5. 따라서 전체 자릿수 합은
6. $23+2\times 192+3\times 146=845$입니다.

헷갈리기 쉬운 점

칸의 개수와 자릿수의 합은 다릅니다. 두 자리 수는 2번, 세 자리 수는 3번 세어야 합니다.

9. 투표 결과

문제 한눈에 보기

7명이 A, B, C 셋 중 한 명에게 투표할 때, A 득표수가 B 득표수보다 큰 경우의 수를 구하는 문제입니다.

답

$897$

핵심 개념

$A>B$와 $A<B$는 대칭입니다. 그래서 $A=B$인 경우만 따로 세면 됩니다.

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

전체 2187가지를 다 세지 않고도 절반 문제로 줄일 수 있기 때문입니다.

단계별 풀이

1. 전체 경우의 수는 $3^7=2187$입니다.
2. $A>B$인 경우와 $A<B$인 경우는 서로 수가 같습니다.
3. 따라서 $A=B$인 경우를 세어 빼면 됩니다.
4. $A=B=k$라고 하면 C는 $7-2k$표를 받습니다.
5. 가능한 $k$는 $0,1,2,3$입니다.
6. 각 경우의 수는
7. $k=0$: $1$
8. $k=1$: $7!/(1!1!5!)=42$
9. $k=2$: $7!/(2!2!3!)=210$
10. $k=3$: $7!/(3!3!1!)=140$
11. 합치면 $393$입니다.
12. 따라서

$A>B=(2187-393)/2=897$

헷갈리기 쉬운 점

$A=B$인 경우는 절반에 넣으면 안 됩니다. 먼저 따로 빼고 나누어야 합니다.

10. 버블 패스

문제 한눈에 보기

길이 3짜리 창을 왼쪽에서 오른쪽으로 움직이며 정렬했을 때, 최종 결과가 $1,2,3,4,5,6,7,8$이 되는 순열의 개수를 세는 문제입니다.

답

$1458$

핵심 개념

숫자 $k$는 최종적으로 $k$번째 자리에 가려면 처음에 너무 오른쪽에 있으면 안 됩니다.

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

한 번 창이 지나간 위치의 왼쪽으로는 더 이상 숫자가 이동해 올 수 없기 때문입니다.

단계별 풀이

1. 숫자 $k$는 왼쪽으로 최대 2칸까지만 이동할 수 있습니다.
2. 따라서 $k$는 처음부터 $k+2$번째 자리 안에는 있어야 합니다.
3. 이것은 순열 $p$에 대해 $p_i\le i+2$와 같은 조건으로 볼 수 있습니다.
4. 이제 왼쪽부터 순열을 채웁니다.
5. 첫째 자리에는 $1,2,3$ 중 하나만 올 수 있으므로 $3$가지입니다.
6. 둘째 자리에는 $1,2,3,4$ 중 남은 것 중 하나가 오므로 다시 $3$가지입니다.
7. 같은 이유로 1번째부터 6번째 자리까지는 각각 $3$가지씩입니다.
8. 7번째 자리는 $2$가지, 마지막은 $1$가지입니다.
9. 따라서 개수는

$3^6\times 2\times 1=1458$

헷갈리기 쉬운 점

길이 3 창 정렬은 완전한 버블 정렬이 아닙니다. 숫자가 왼쪽으로 너무 멀리 이동할 수는 없습니다.

11. 거리 점프

문제 한눈에 보기

함수 $f$를 10번 반복했을 때 0이 되는 정수 $x$들을 모두 찾아, 그 개수와 합을 더하는 문제입니다.

답

$1410$

핵심 개념

앞으로 가기보다 $0$으로 들어오는 값들을 거꾸로 찾는 것이 쉽습니다.

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

$f^{10}(x)=0$인 $x$를 직접 찾는 것은 어렵지만, $0$의 역상(preimage)을 반복하면 규칙이 보입니다.

단계별 풀이

1. 한 번 점프해서 0이 되려면 처음 값은 $20,21,22,23,24,25$뿐입니다.
2. 이 집합의 역상을 다시 구하면 $-5,-4,-3,-2,-1,0,45,46,47,48,49,50$이 나옵니다.
3. 이런 식으로 거꾸로 10번 반복하면 길이 6짜리 구간이 10개 생깁니다.
4. 최종 집합은

$[-205,-200],[-155,-150],[-105,-100],[-55,-50],[-5,0],[45,50],[95,100],[145,150],[195,200],[245,250]$

입니다. 각 구간은 양 끝을 포함합니다. 5. 그래서 개수 $c$는 $10\times 6=60$입니다. 6. 각 구간의 합을 더하면 전체 합 $s=1350$입니다. 7. 따라서 $c+s=60+1350=1410$입니다.

헷갈리기 쉬운 점

문제에서 $x$는 모든 정수입니다. 음수도 포함됩니다.

12. 개구리 점프

문제 한눈에 보기

점프를 여러 번 해서 만들 수 있는 서로 다른 개구리 배치의 개수를 세는 문제입니다.

답

$5005$

핵심 개념

개구리들은 서로의 순서를 바꾸지 못합니다. 결국 바뀌는 것은 빈칸이 어디로 이동했는가입니다.

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

점프를 직접 전부 써 보는 것은 너무 많지만, 순서가 보존된다는 사실을 이용하면 조합 문제로 바뀝니다.

단계별 풀이

1. 점프는 개구리 둘을 뛰어넘는 이동이므로, 개구리들의 왼쪽부터의 순서는 변하지 않습니다.
2. 따라서 상태를 정하는 것은 “어느 자리에 빈칸들이 놓여 있느냐”입니다.
3. 이 구조를 정리하면, 가능한 상태 수는 결국 조합

$C(15,6)$

으로 계산됩니다. 4. 계산하면

$C(15,6)=5005$

입니다.

헷갈리기 쉬운 점

개구리들은 서로 구별하지 않지만, 왼쪽에서 몇 번째 개구리인가라는 순서는 유지됩니다.

13. 오르막길

문제 한눈에 보기

화살표가 가리키는 방향으로 갈수록 가중치가 더 커지게 정점들에 숫자를 붙이는 문제입니다.

답

한 가지 정답은 해설 그림과 같은 배치입니다.

핵심 개념

이 문제는 사실상 DAG의 레벨을 매기는 문제입니다.

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

들어오는 간선이 없는 쪽부터 작은 수를 주면 조건을 자연스럽게 만족시킬 수 있습니다.

단계별 풀이

1. 먼저 가장 앞층에 있어야 하는 정점들에 $1$을 줍니다.
2. 그 정점들 뒤에 와야 하는 정점들에 $2$, 그다음에 $3$, $4$를 줍니다.
3. 해설 그림의 배치는 모든 간선 $A\to B$에 대해 B의 값이 더 크게 되도록 만든 한 가지 예시입니다.

헷갈리기 쉬운 점

같은 층에 있는 정점끼리는 같은 숫자를 받아도 괜찮습니다.

14. 트리 높이 줄이기

문제 한눈에 보기

간선 길이를 줄여 트리 높이를 10 이하로 만들되, 비용을 최소화하는 문제입니다.

답

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

핵심 개념

여러 가장긴 경로가 함께 지나는 간선을 먼저 줄여야 합니다.

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

한 번 줄일 때 여러 깊은 경로가 동시에 짧아지면 비용 대비 효과가 가장 큽니다.

단계별 풀이

1. 루트에서 리프까지의 경로 길이 중 가장 긴 것들을 찾습니다.
2. 그 경로들에 공통으로 들어 있는 간선을 우선 줄입니다.
3. 공통 간선을 줄일 수 없을 때는, 여전히 가장 긴 경로에 들어 있는 간선을 줄입니다.
4. 해설 그림처럼 하면 총 비용 $5$로 높이를 $10$까지 낮출 수 있습니다.

헷갈리기 쉬운 점

가장 큰 간선을 무조건 줄이는 것이 아니라, 높이를 실제로 줄이는 간선을 골라야 합니다.

15. 사탕 놓기

문제 한눈에 보기

누적합 표 $S(i,j)$가 주어졌을 때, 실제 사탕 배치를 복원하는 문제입니다.

답

한 가지 복원 결과를 행별 0,1 문자열로 쓰면 다음과 같습니다.

$01111110$ $11000010$ $01101100$ $10100011$ $01001010$ $01100100$ $00010100$ $10001000$

핵심 개념

2차원 누적합의 역연산을 하면 됩니다.

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

표에 적힌 값은 “왼쪽 위 직사각형의 총합”이므로, 포함-배제를 쓰면 한 칸 값을 다시 얻을 수 있습니다.

단계별 풀이

1. 실제 칸 값 $a(i,j)$는

$S(i,j)-S(i-1,j)-S(i,j-1)+S(i-1,j-1)$

입니다. 2. 이 식을 각 칸에 적용하면 값이 $0$ 또는 $1$로 정해집니다. 3. 예를 들어 $(4,2)$의 값은 $5-4-2+1=0$이어서 빈칸입니다. 4. 모든 칸에 대해 같은 계산을 하면 위 배치가 나옵니다.

헷갈리기 쉬운 점

왼쪽 위 부분을 두 번 빼기 때문에 마지막에 한 번 다시 더해야 합니다.

16. 포크

문제 한눈에 보기

배열에서 $(i,i+2)$ 꼴의 두 원소만 함께 고를 수 있을 때, 겹치지 않게 골라 합을 최대로 만드는 문제입니다.

답

해설 그림의 최댓값은 $42$입니다.

핵심 개념

전형적인 일차원 DP입니다.

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

어떤 자리를 고르면 그다음 두 자리 근처 선택이 막히므로, “선택/비선택” 비교가 자연스럽게 생깁니다.

단계별 풀이

1. $\mathrm{dp}[i]$를 $i$번째부터 끝까지 보았을 때 얻을 수 있는 최대합이라고 둡니다.
2. 그러면 두 선택지가 있습니다.
3. $i$를 건너뛰면 $\mathrm{dp}[i+1]$
4. $i$를 고르면 $a[i]+a[i+2]+\mathrm{dp}[i+3]$
5. 따라서

$\mathrm{dp}[i]=\max (\mathrm{dp}[i+1],a[i]+a[i+2]+\mathrm{dp}[i+3])$

입니다. 6. 이 식으로 뒤에서부터 계산하면 최댓값이 $42$가 됩니다.

헷갈리기 쉬운 점

$i$를 고르면 $i+1$만 못 고르는 것이 아니라 $i+2$도 이미 함께 고른 상태가 됩니다.

17. 실 태우기

문제 한눈에 보기

실 위의 20개 후보 지점 중 4개를 골라, 실 전체가 다 타는 시간을 최소로 만드는 문제입니다.

답

한 가지 최적 선택은 $13,40,67,92$이고, 최종 시간은 $13.5$초입니다.

핵심 개념

전체 시간은 끝 구간과 불 사이 구간 절반 중 가장 큰 값입니다.

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

가장 늦게 타는 곳이 전체 시간을 결정하므로, 가장 긴 빈 구간을 줄이는 것이 핵심입니다.

단계별 풀이

1. 선택한 점들을 $x1<x2<x3<x4$라고 하겠습니다.
2. 전체 시간이 되는 값은

$\max (x1,(x2-x1)/2,(x3-x2)/2,(x4-x3)/2,100-x4)$

입니다. 3. 해설의 선택 $13,40,67,92$에 대해 계산하면 4. $13,13.5,13.5,12.5,8$이 나옵니다. 5. 따라서 전체 시간은 $13.5$초입니다.

헷갈리기 쉬운 점

중간 구간은 한쪽에서만 타는 것이 아니라 양쪽에서 동시에 타 들어옵니다.

18. 올바른 괄호 문자열

문제 한눈에 보기

문자 몇 개를 뒤집어서 올바른 괄호 문자열로 만들 때, 필요한 최소 횟수를 구하는 문제입니다.

답

최소 행동 횟수는 $6$입니다.

핵심 개념

접두사 균형(balance)을 보면서 greedy하게 고칠 수 있습니다.

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

올바른 괄호 문자열은 어떤 앞부분에서도 닫는 괄호가 더 많아질 수 없습니다.

단계별 풀이

1. 왼쪽부터 보며 (는 $+1$, )는 $-1$로 생각합니다.
2. 합이 처음 음수가 되는 순간, 그 앞부분의 ) 하나는 반드시 (로 바뀌어야 합니다.
3. 이 과정을 반복하면 접두사 조건을 모두 만족시킬 수 있습니다.
4. 그다음 전체 ( 개수와 ) 개수가 다르면, 뒤쪽에서 필요한 만큼 다시 바꿉니다.
5. 해설의 문자열은 최소 $6$번 바꾸면 올바른 괄호 문자열이 됩니다.

헷갈리기 쉬운 점

전체 개수만 맞아도 안 되고, 모든 앞부분 조건도 함께 맞아야 합니다.

19. 버블 거울 정렬

문제 한눈에 보기

인접한 두 카드를 뒤집으며 자리를 바꾸는 연산으로, 오름차순 정렬과 앞면 조건을 동시에 만족시키는 문제입니다.

답

한 가지 최적 답은 다음 $26$회입니다.

$8,7,2,1,5,4,3,2,6,5,4,3,9,8,7,6,5,4,11,10,6,7,9,8,9,11$

핵심 개념

버블 정렬과 뒤집힘 상태 관리가 동시에 들어 있는 문제입니다.

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

숫자만 정렬되면 끝나는 것이 아니라, 마지막엔 모든 카드가 앞면이어야 합니다.

단계별 풀이

1. 인접 swap을 하면서 큰 수를 오른쪽으로 보내는 구조는 버블 정렬과 비슷합니다.
2. 그런데 swap할 때마다 두 카드의 앞뒤도 함께 바뀌므로, 정렬 과정 중 뒤집힘도 같이 바로잡아야 합니다.
3. 해설이 제시한 26회 순서는 두 조건을 동시에 만족하는 최적 예시입니다.

헷갈리기 쉬운 점

정렬만 끝나고 카드가 뒷면으로 남아 있으면 정답이 아닙니다.

20. 수식 최대화

문제 한눈에 보기

빼기 기호로만 이어진 수식에 괄호를 적절히 넣어 값을 최대화하는 문제입니다.

답

부분문제 1의 최댓값은 $34$, 부분문제 2의 최댓값은 $84$입니다.

해설의 한 가지 정답은 다음과 같습니다.

부분문제 1: $3-(1-4-1-5-9-2-6)-(-5)$

부분문제 2: $2-(-7-(-1-8-2-8)-(-1)-(-8-2)-(-8-4)-(-5)-(-9-4-5-2)-(-3-5))$

핵심 개념

빼기 뒤에 큰 덩어리를 괄호로 묶으면, 그 덩어리 전체가 부호가 바뀌어 유리해집니다.

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

$a-(b-c-d)$처럼 묶으면 뒤의 여러 음수가 한꺼번에 플러스로 바뀔 수 있기 때문입니다.

단계별 풀이

1. 괄호가 없으면 앞에서부터 그냥 빼기만 하게 됩니다.
2. 그런데 - ( ... ) 형태를 만들면 괄호 안의 값이 전체적으로 한 번 더 부호가 바뀝니다.
3. 그래서 뒤쪽의 음수 묶음을 크게 만들어 줄수록 값이 커집니다.
4. 해설 그림의 괄호 배치를 적용하면 부분문제 1은 $34$, 부분문제 2는 $84$가 됩니다.

헷갈리기 쉬운 점

괄호를 많이 친다고 항상 좋은 것이 아닙니다. 부호가 실제로 어떻게 바뀌는지 계산해 봐야 합니다.

개념 한눈에 보기

개념	나온 문제	기억할 말
제곱수	1	45² 다음은 46², 47²이다.
스택	2	나중에 들어간 것이 먼저 나온다.
식 세우기	3	기준 산 하나를 정해 모두 표현한다.
속력 비	4	같은 시간의 거리 비가 속력 비다.
역추적	5	끝 문자열에서 시작해 되돌아간다.
사전식 순서	6	큰 수부터 묶어 가며 몇 번째인지 찾는다.
최대공약수	7	나머지 조건은 차이의 배수 조건이다.
자릿수 세기	8	한 자리, 두 자리, 세 자리 개수를 분리한다.
대칭	9	$A>B$와 $A<B$는 같은 수다.
이동 한계	10	숫자 $k$는 처음에 $k+2$ 안에 있어야 한다.
역상 집합	11	$f^{10}(x)=0$은 0의 역상을 거꾸로 찾는다.
조합 상태 수	12	순서 보존을 이용해 조합 문제로 바꾼다.
DAG 레벨	13	앞층부터 작은 수를 준다.
공통 경로	14	여러 깊은 경로가 함께 지나는 간선을 줄인다.
2차원 누적합	15	S - 위 - 왼쪽 + 왼쪽위를 쓴다.
일차원 DP	16	선택 / 건너뛰기 둘 중 큰 쪽을 고른다.
최대 구간 길이	17	가장 늦게 타는 구간이 답을 정한다.
balance 그리디	18	접두사 합이 음수가 되면 꼭 고쳐야 한다.
정렬 + 상태	19	숫자 순서와 앞면 조건을 함께 만족시킨다.
괄호와 부호	20	- ( ... )는 뒤의 부호를 한 번 더 바꾼다.