2026년 1월 BOJ 정리

연말에도 백준을 했듯이, 연초에도 백준을 합니다. 이번에는 지난 달과 달리 푼 날짜 순으로 정리하여 서사성을 살리려고 합니다. 찾고자 하는 문제가 있다면 Ctrl+F로 찾으시면 되겠습니다. 이번 달은 하루에 5문제 이상 푸는 것을 목표로 했고, 총 165문제를 풀었습니다. 스포일러에 주의하세요!

1월 1일

35031. But when she jumps it gets faster (G2)

2026년의 1번째 문제입니다. 새해 첫 문제로 무엇을 풀지 고민하다가, Goodbye, BOJ! 2025에서 풀지 못한 B번 문제인 #35031을 업솔빙하기로 했습니다. 일단 최적화하지 않은 나이브는 $O(NL)$의 시간이 걸립니다. 하지만 나이브 외의 특별한 해결책이 보이지 않으니, 나이브를 최대한 최적화해 봅시다.

현재 영상이 $T$배속일 때, 캐릭터 점프 횟수의 누적 합을 이용해 $T$개의 장면을 $O(1)$에 처리할 수 있다면 어떨까요? 가장 시간이 오래 걸리는 경우는 마지막 프레임에 점프 한 번이 있는 경우일 것입니다. 이때의 시간 복잡도는 $\displaystyle O(\sum_{k=1}^N \frac{L}{k})$ 정도 될 것이고, 조화급수를 이용하면 대략 $O(L\log{}N)$이 됩니다!

$T$개의 장면이 지난 전과 후의 장면 번호를 비교하여 적절하게 누적 합 처리를 해주어 AC를 받았습니다. 난이도는 G2라기에는 로그 시간에 된다는 아이디어 찾기가 어려운 것 같아 G1을 기여했습니다.

1956. 운동 (G4)

2026년의 2번째 문제입니다. 최단 사이클을 찾는 문제인데, 사이클의 정의를 생각해 보면 두 정점 $A$와 $B$에 대해서 $(A\to{}B의~거리)+(B\to{}A의~거리)$를 최소화해야 함을 알 수 있습니다. 따라서 플로이드-워셜로 모든 정점 쌍의 거리를 구한 다음, 임의의 두 정점을 나이브하게 잡아 최단 사이클을 구했습니다. 시간 복잡도는 플로이드-워셜의 $O(V^3)$입니다. 난이도는 다익스트라 or 플로이드의 기본 티어보다 하나 높은 G3를 기여했습니다.

30917. A+B - 10 (제1편) (B3)

2026년의 3번째 문제입니다. 인생 최초의 인터랙티브 문제이기도 합니다. 코드포스 라운드 공지를 읽다 보면 인터랙티브 문제가 있다는 말이 종종 나오는데, 그때마다 인터랙티브를 몰라 참가하지 못했던 기억이 있습니다. 그래서 인터랙티브에 익숙해져 보려고 합니다.

문제 자체는 매우 쉽습니다. ? A x와 ? B x를 $x=1,2,\cdots,9$까지 모두 출력해 주고, 입력에 따라 $A$와 $B$의 값을 특정한 뒤 $A+B$의 값을 ! x 형식으로 출력하면 됩니다. 난이도는 B3를 기여했습니다.

23306. binary는 호남선 (S2)

2026년의 4번째 문제입니다. 문제에서는 $\lfloor\log_2N\rfloor$번의 질문을 할 수 있다고 했지만, 사실 2번만 질문해도 됩니다. 맨 앞과 맨 뒤를 물어본 뒤, 더 높은 쪽을 따라 답을 내면 됩니다. 평탄한 구간을 하나로 합치면 반드시 지그재그 형태가 되기 때문입니다. 난이도는 S2가 overrated라 생각해 S3를 기여했습니다.

12014. 주식 (G2)

2026년의 5번째 문제입니다. 주어진 수열의 LIS 길이가 $K$ 이상인지 묻는 문제입니다. DP와 이분 탐색을 활용해 $O(N\log{}N)$에 LIS를 구해 주면 됩니다. 난이도는 $O(N\log{}N)$ LIS 기본 문제와 같은 G2를 기여했습니다.

1월 2일

20303. 할로윈의 양아치 (G2)

2026년의 6번째 문제입니다. 정점에 가중치가 있고 간선에 가중치가 없는 무향 그래프가 주어질 때, 몇 개의 연결 요소를 골라 가중치 합을 최대로 하는 문제입니다. 이때 정점 개수가 $K$ 이상일 수 없습니다. BFS나 DFS를 적당히 돌려 연결 요소를 찾고, 냅색 문제를 해결하면 됩니다. 난이도는 BFS/DFS + 냅색 + 약간의 아이디어라 생각해 G3를 기여했습니다.

9625. BABBA (S5)

2026년의 7번째 문제입니다. A와 B의 개수가 피보나치 수와 같다는 것을 쉽게 알 수 있습니다. 마침 $K$의 제한도 $45$로 매우 작으므로 $O(K)$에 구해주면 됩니다. 난이도는 S5를 기여했습니다.

5557. 1학년 (G5)

2026년의 8번째 문제입니다. $dp[i][j]$를 $i$번째 수까지 보았을 때, 정답이 $j$인 식의 개수로 합시다. 이때 $0\le{}j\le{}20$일 때만 저장해 줍시다. 점화식을 어떻게 세울지는 +와 -를 고려한다는 점에서 매우 자명하기도 하고, 식으로 나타내기도 까다로워 생략하겠습니다. 시간 복잡도 $O(N)$의 DP로 문제를 해결할 수 있고, 최종 출력은 $dp[N-1][N번째~수]$입니다. 난이도는 기존 G5보다 한 단계 낮은 S1을 기여했습니다.

11060. 점프 점프 (S2)

2026년의 9번째 문제입니다. 탑다운 DP를 이용해 풀면 되는 간단한 문제입니다. $f(x)$를 x번 위치에서의 최소 이동 횟수라 합시다. 배열의 $x$번째 값이 $k$라 할 때, $\displaystyle f(x)=\min_{m=1}^kf(x+m)+1$입니다. 시간 복잡도는 $O(N)$입니다. BFS로도 해결할 수 있다고 하네요. 난이도는 충분히 많은 사람들이 동의한 S2를 기여했습니다. solved.ac를 확인해 보니, 이 문제로 1700솔브를 달성했습니다!

24365. ПЧЕЛИЧКАТА МАЯ (B4)

2026년의 10번째 문제입니다. 원래는 오늘 새해 첫 플래를 풀려 했지만, 다른 할 일이 많아 브론즈 2문제만 더 밀기로 했습니다. 이 문제도 브론즈답게 매우 단순합니다. 오른쪽 꽃에 벌이 가장 많으므로, 가운데로 보내야 하는 벌의 수와 왼쪽으로 보내야 하는 벌의 수를 각각 계산해 주면 됩니다. 가운데에서 왼쪽으로 벌을 옮겨야 하는 경우는 어떻게 되냐고 물을 수 있지만, 음수 마리만큼 옮긴다 생각하면 동일하게 처리 가능합니다. 난이도는 B4의 관찰이 아니라 생각해 B3를 기여했습니다.

34795. An Elephant Problem (B4)

2026년의 11번째 문제입니다. $\lceil\frac{d}{m}\rceil$을 구해 주면 됩니다. 난이도는 B4를 기여했습니다.

1월 3일

2143. 두 배열의 합 (G3)

2026년의 12번째 문제입니다. Class 5에 있는 문제인데, 골드 정도의 문제를 확실하게 푸는 연습을 하기 위해 Class 5를 돌고 있습니다. 가능한 쌍의 개수는 $O(n^2m^2)$이므로 누적 합을 사용해 구간 합을 $O(1)$에 구하더라도 나이브한 방법을 쓰면 시간 내에 통과하지 못합니다.

위 방법을 어떻게 최적화할 수 있을까요? C++의 map이나 Python의 dict를 이용해 각 배열에 대해 부분합별 경우의 수를 구해 놓습니다. 이것을 만드는 데는 $O(n^2+m^2)$의 시간이 걸리고, 배열 $A$에서 나올 수 있는 각 부분합 $s$에 대해 배열 $B$에 부분합 $T-s$가 있는지 검사하는 데 $O(n^2)$의 시간이 걸립니다. $n=m$이라 하면 전체 문제를 $O(n^2)$에 해결할 수 있습니다. 난이도는 G3를 기여했습니다.

34455. Donut Shop (B4)

2026년의 13번째 문제입니다. 갑자기 가족 여행이 잡혀 5문제를 1시간 만에 풀어야 했고, B5는 이미 모두 풀었기 때문에 B4를 풀기로 했습니다. 정수 $D$를 저장해 놓고, $E$개의 쿼리마다 $D$값을 갱신하면 됩니다. 난이도는 #10950 같은 쿼리 문제도 B5에 있음을 고려해 B5를 기여했습니다.

34798. Missed Alarm (B4)

2026년의 14번째 문제입니다. 시간을 먼저 비교하고, 분을 비교하면 되는 간단한 문제입니다. 난이도는 B4를 기여했습니다.

31281. ЗЛАТНАТА СРЕДА (B4)

2026년의 15번째 문제입니다. 세 수의 중앙값을 구하는 문제입니다. $(a+b+c)-\min(a,b,c)-\max(a,b,c)$가 답이 됩니다. 난이도는 #2752와 같은 B4를 기여했습니다.

34161. OO0OO (B4)

2026년의 16번째 문제입니다. 회문에 대한 이야기를 하려는 척 하다가 <이상한 변호사 우영우>의 향고래 문제가 되는 난해한 지문의 문제입니다. 사실 정답은 문제에 이미 나와 있습니다. $A,B,C,D$의 값에 관계없이 고래는 알을 낳을 수 없습니다. 따라서 -1을 $10000$번 출력하면 됩니다. 난이도는 지문이 난해하고 일반적인 PS와 거리가 매우 먼 문제임을 감안하여 NR을 기여했습니다.

26736. Wynik meczu (B4)

2026년의 17번째 문제입니다. 주어진 문자열을 끝까지 읽으면서 A와 B의 개수를 각각 세어 주면 됩니다. 난이도는 새싹 문제와 유사하다 생각해 B5를 기여했습니다.

34934. 신규 학과 (B4)

2026년의 18번째 문제입니다. 원래는 풀고자 했던 문제 수를 모두 채웠으나, #34161이 언제 NR에 갈지 몰라 한 문제를 더 풀기로 했습니다. 문제는 매우 단순한데, 개설 연도가 $2026$인 학과가 정확히 한 개 있으므로 그것을 출력하면 됩니다. 난이도는 B4를 기여했습니다.

1월 4일

1958. LCS 3 (G4)

2026년의 19번째 문제입니다. 이번에는 과거에 실패했던 문제들을 풀기로 했습니다. 세 문자열의 LCS 길이를 구하는 문제인데, 원래는 두 문자열의 LCS를 구하고 그 결과와 마지막 문자열의 LCS 길이를 구하고자 했습니다. 그러나 이렇게 하면 처음 두 문자열의 LCS가 여러 개일 수 있으므로 AC를 받지 못합니다.

따라서 세 문자열이 각각 $S_1,S_2,S_3$일 때 $O(|S_1||S_2||S_3|)$의 알고리즘을 사용해 줍시다. 먼저 세 문자열을 각각 $x$, $y$, $z$번째까지 보았을 때의 LCS 길이를 $dp[x][y][z]$라 정의합니다. 그러면 $S_1[x]$, $S_2[y]$, $S_3[z]$가 모두 같을 때 $dp[x][y][z]=dp[x-1][y-1][z-1]+1$이고, 그렇지 않을 때 $dp[x][y][z]=\max(dp[x-1][y][z],dp[x][y-1][z],dp[x][y][z-1])$입니다. 난이도는 #9251보다 한 단계 높은 G4를 기여했습니다.

28280. 귀납법 (S1)

2026년의 20번째 문제입니다. $1$부터 $4\times10^6$까지의 각 정수를 정점으로, 2배를 하거나 1을 빼는 조작을 간선으로 하여 BFS를 하면 됩니다. 기존에는 방문 처리를 Python의 set (C++의 unordered_set과 같은 해시 집합입니다)으로 하여 시간 초과를 받았습니다. 이것을 배열로 바꾸어 주면 AC를 받을 수 있습니다. Wrong Proof!를 출력하는 경우는 없으므로, 그 부분은 처리할 필요가 없습니다. 난이도는 #1697과 같은 S1을 기여했습니다.

24293. ВСЕКИ ТРЕТИ (S4)

2026년의 21번째 문제입니다. 기존에는 Python의 str에서 문자열을 뒤집고 삭제하는 것을 직접 구현하여 TLE를 받았습니다. 문자열을 지우는 것에 덱을 사용하면 $O(N)$에 문제를 해결할 수 있습니다. 난이도는 덱을 구현하는 문제인 #10866이 S4인 것을 고려해 S3를 기여했습니다. 원래 이 문제의 난이도가 S3였는데, 제가 S3를 기여하니 S4가 되더라고요? 왜 그런지는 아직 모르겠습니다.

14470. 전자레인지 (B4)

2026년의 22번째 문제입니다. 오늘도 어김없이 현생 이슈가 찾아왔고, 미루고 있던 랜덤 마라톤 A와 B번을 풀기로 했습니다. 고기의 최종 온도는 항상 양수이므로, 초기에 얼어 있는지 얼어 있지 않은지만 확인하여 조건 분기를 해 주면 됩니다. 난이도는 B4를 기여했습니다.

2097. 조약돌 (S5)

2026년의 23번째 문제입니다. 랜덤 마라톤의 B번 문제이기도 합니다. $N$이 작을 때를 직접 그리면서 생각해 보았고, 가로 길이와 세로 길이의 차이가 최대 $1$이어야 한다는 것을 알게 되었습니다. 따라서 한 변의 길이가 $1$인 정사각형에서 시작해 각 변의 길이를 번갈아서 $1$씩 늘려 나가는 방식으로 AC를 받을 수 있습니다. 시간 복잡도는 $O(\sqrt{N})$입니다. 난이도는 S5를 기여했습니다. A와 B의 난이도 격차가 상당하네요...

1월 5일

26205. Eliminating Ballons (G5)

2026년의 24번째 문제입니다. 어제에 이어 전에 실패했던 문제들을 풀기로 합니다. 지문을 읽어보면 Balloon과 Ballon이 섞여 있습니다. 왜 그럴까요... 문제를 해석해 보면, 주어진 수열을 가장 적은 수의 부분 수열(연속할 필요는 없습니다)로 나누어 각 부분 수열의 공차가 -1이 되도록 하는 문제임을 알 수 있습니다. 그리디 알고리즘으로 해결할 수 있는데, 길이 $10^6+1$의 배열 $D$를 만든 뒤 수열의 앞에서부터 보면서 아래 과정을 반복해 줍시다.

1. 현재 보고 있는 원소의 값을 $x$라 하자.
2. $D_{x+1}>0$이면 $D_{x+1}$에서 $1$을 빼고, 그렇지 않으면 결과값에 $1$을 더한다.
3. $D_x$에 $1$을 더한다.

기존에는 해시맵을 썼다가 틀렸는데, 다시 짜니 바로 AC를 받았습니다. 태그에 해시맵이 있는 것을 보니 이것이 WA의 원인은 아닌데 말이죠... 난이도는 G5를 기여했습니다.

11509. 풍선 맞추기 (G5)

2026년의 25번째 문제입니다. #26205의 기여를 보니 이 문제와 거의 같다는 말이 많기에 풀기로 했는데, 문제를 읽어 보니 $N$ 제한 빼고는 완전히 같은 것 같아 전 코드를 그대로 냈습니다. 그리고 바로 AC를 받았습니다. 문제를 읽어보니 #26205에는 #11509와 달리 모든 풍선의 높이가 다르다는 조건이 있더라고요? 하지만 문제 풀이에 영향을 주지 않는다고 판단했고, 난이도는 #26205와 같은 G5를 기여했습니다.

16890. 창업 (G1)

2026년의 26번째 문제입니다. 기존에는 자신의 문자 중 사전순으로 가장 앞/뒤에 오는 것을 회사 이름 빈칸 중 가장 앞에 넣도록 했는데, 이것은 구사과의 모든 문자가 큐브러버보다 뒤에 오게 되는 상황을 고려하지 못합니다. 따라서 다른 해결책을 생각해야 합니다. 먼저 구사과는 사전순으로 앞에 오는 $\lfloor\frac{N+1}{2}\rfloor$개의 문자, 큐브러버는 사전순으로 뒤에 오는 $\lfloor\frac{N}{2}\rfloor$개의 문자를 써야 합니다. 따라서 이 밖의 문자는 존재하지 않는다고 생각합시다.

이제 구사과의 입장에서 생각해 봅니다. 구사과의 문자 중 가장 앞에 있는 것이 큐브러버의 문자 중 가장 뒤에 있는 것보다 작다면, 구사과는 자신의 문자 중 가장 작은 것을 맨 앞 빈칸에 놓는 것이 최선입니다. 그러나 그렇지 않다면, 어차피 앞쪽을 큐브러버가 채울 것이므로 굳이 자신이 큰 문자로 앞을 채울 이유가 없습니다. 따라서 자신의 문자 중 가장 큰 것을 맨 뒤 빈칸에 놓는 것이 최선입니다. 난이도는 G1을 기여했습니다.

25178. 두라무리 휴지 (S5)

2026년의 27번째 문제입니다. 앞 3문제 동안 실패한 문제 개수를 줄였으니, 랜덤 마라톤 C, D만 풀고 마치려 합니다. 이 문제는 C번인데, 문제에서 요구하는 대로 구현하면 됩니다. 두 단어를 정렬했을 때 같고, 시작 글자와 끝 글자가 같으며, 모음을 제거했을 때 같으면 YES를, 그렇지 않으면 NO를 출력합니다. 난이도는 S5를 기여했습니다.

10211. Maximum Subarray (S4)

2026년의 28번째 문제입니다. 앞선 C번에 이어 랜덤 마라톤 D번 문제입니다. #1912의 테스트 케이스 버전처럼 생겼으나, 사실 $N$ 제한이 $1000$밖에 안 되기 때문에 누적 합을 사용한 $O(N^2)$ 브루트 포스가 통과합니다. 난이도는 누적 합 기본 문제인 #11659와 같은 S3를 기여했습니다.

2034. 반음 (S4)

2026년의 29번째 문제입니다. 원래는 #10211에서 오늘의 PS를 끝내려 했는데, 할 일이 없어 한 문제만 더 풀기로 했습니다. 랜덤 마라톤 E번입니다. 주어진 악보가 흰 건반만으로 연주 가능하도록 첫 음을 설정하는 문제인데, 가능한 첫 음이 A~G의 7개밖에 없으므로 모두 다 해보면 됩니다. 난이도는 S4를 기여했습니다.

1월 6일

2150. Strongly Connected Component (P5)

2026년의 30번째 문제입니다. 오늘은 SCC를 배워 보기로 했습니다. 이 블로그를 참고하여, 코사라주 알고리즘을 사용했습니다. 난이도는 P5를 기여했습니다.

4196. 도미노 (P4)

2026년의 31번째 문제입니다. SCC 태그의 문제 중 2번째로 많이 풀린 문제이기도 합니다. 그래프에서 indegree가 $0$인 정점의 개수를 구하면 됩니다. 한 SCC 내의 두 정점끼리는 자유롭게 이동할 수 있으며, 각 SCC를 하나의 정점으로 보면 그래프를 DAG로 만들 수 있습니다. 따라서 주어진 그래프의 SCC를 모두 구한 뒤 DAG에서 indegree가 $0$인 SCC의 개수를 구하면 됩니다. 난이도는 P4를 기여했습니다.

31229. 또 수열 문제야 (S5)

2026년의 32번째 문제입니다. SCC 문제는 후에 더 풀도록 하고, 내일 있는 코드포스를 대비해 해 구성하기 + 애드 혹 문제를 풀기로 했습니다. 길이 $N$의 수열을 출력하면 되는데, 모든 원소는 서로 달라야 하고 어떤 두 원소의 합도 둘의 곱의 약수가 되어서는 안 됩니다. 이 조건에서 모든 원소가 $3$ 이상의 홀수이면 되지 않을까 생각했습니다. $3$ 이상의 두 자연수 $a$, $b$에 대하여 $a+b<ab$인데, $a+b$는 짝수이고 $ab$는 홀수가 되기 때문입니다. 따라서 $3,5,7,\cdots$을 순서대로 출력하면 됩니다. 난이도는 S4를 기여했습니다.

27966. △ (S3)

2026년의 33번째 문제입니다. 이번에도 해 구성하기 + 애드 혹입니다. 직관적으로 하나의 정점에 다른 모든 정점이 매달린 형태가 최적일 것이라고 생각했고, 이때 모든 정점 쌍의 거리 합은 $(N-1)+2\times\frac{(N-1)(N-2)}{2}=(N-1)(N-1)=(N-1)^2$입니다. 증명은 Proof by AC로 대체했습니다. 난이도는 S3를 기여했습니다.

31288. 캬루 (S2)

2026년의 34번째 문제입니다. $N$자리 소수에서 한 자리만 바꾸어 소수가 아니게 만드는 문제인데, 이러한 수를 $N$개 출력해야 합니다. 가장 먼저 할 수 있는 발상은 각 자리 수를 바꾸는 조작을 한 번씩 하는 것입니다. 하지만 $100$자리 소수까지 나올 수 있기 때문에 일일히 소수 판정을 할 수는 없습니다. 어떻게 해야 할까요? 먼저 $N=1$일 때는 $4$나 $8$, $9$와 같은 아무 합성수나 출력하면 됩니다. 그러므로 $N>1$일 때만 생각해 봅시다.

$3$의 배수는 각 자리 수의 합이 $3$의 배수입니다. 입력으로 주어지는 수는 소수이므로 $3$의 배수가 아니고, 따라서 임의의 자리 수를 $1$만큼 빼거나 더하면 $3$의 배수가 됩니다! 따라서 각 자리 수의 합을 미리 구한 뒤 자리마다 이 작업을 수행하면 되고, 만약 불가능하다면 $1$을 빼는 것은 $2$를 더하는 것으로, $1$을 더하는 것은 $2$를 빼는 것으로 대체하면 됩니다. 맨 앞 자리의 경우에는 자리 수가 $0$이 되면 안 되는 것도 고려해줍시다. 난이도는 S3를 기여했습니다.

1월 7일

11277. 2-SAT - 1 (S1)

2026년의 35번째 문제입니다. 어제 SCC를 배웠으니, SCC의 대표적인 응용인 2-SAT을 풀기로 했습니다. 백준에는 2-SAT 문제가 1번부터 4번까지 있는데, 이 문제가 1번입니다. 사실 이 문제는 SCC를 사용할 필요가 없습니다.$N$이 $20$ 이하로 매우 작기 때문에 모든 경우의 수를 시도해 보면 됩니다. 시간 복잡도는 $2^NM$입니다. 난이도는 S1을 기여했습니다.

11278. 2-SAT - 2 (S1)

2026년의 36번째 문제입니다. #11277과 제한이 같고, 실제 가능한 경우를 출력해야 하는 것이 다릅니다. #11277을 브루트 포스로 풀었으니, 출력만 추가하면 됩니다. 난이도는 #11277과 같은 S1을 기여했습니다.

11280. 2-SAT - 3 (P4)

2026년의 37번째 문제입니다. #11277과 달리 이번 문제는 $N$의 제한이 크기 때문에 SCC를 사용해야 합니다. 구체적인 방법은 이 블로그에 정리되어 있습니다. 난이도는 #2150보다 한 단계 높은 P4를 기여했습니다.

12796. 나의 행렬곱셈 답사기 (G5)

2026년의 38번째 문제입니다. 코드포스 당일이니만큼 해 구성하기와 그리디 문제를 하나씩 풀기로 했습니다. 이 문제는 애드 혹 + 해 구성하기 중에는 쉬운 편인 것 같습니다. $(K+1)\times1,1\times1,1\times1$ 행렬을 곱한다고 하면 최적의 곱셈 횟수가 $K+2$, 최악의 횟수가 $2K+2$번이 됩니다. 난이도는 G4를 기여했습니다.

1461. 도서관 (G4)

2026년의 39번째 문제입니다. 만약 책의 위치가 양수뿐이라면, 멀리 있는 것부터 $M$개씩 운반하는 것이 최선일 것입니다. 그러나 양수 위치의 책과 음수 위치의 책을 함께 옮길 때는 반드시 위치 $0$을 불필요하게 지나게 되니, 양수 따로 음수 따로 운반하며 위 기준을 적용해 줍시다. 또한 마지막에는 위치 $0$에 돌아올 필요가 없으므로, 전체 책 위치 중 절댓값이 최대인 것을 빼서 출력합시다. 난이도는 G4를 기여했습니다.

1월 8일

27527. 배너 걸기 (S1)

2026년의 40번째 문제입니다. 오늘은 리롤된 랜덤 마라톤 H번만 빠르게 풀고 B4 문제를 밀기로 했습니다. 모든 가능한 경우를 직접 확인하는 것 외에는 방법이 없어 보이는데, 나이브하게 하면 시간 복잡도가 $O(NM)$이 됩니다. 이렇게 하면 TLE가 나게 되니 다른 방법을 생각해 봅시다.

배열 $B$를 만들어, $B_i$를 현재 구간에서 $A_k=i$인 $k$의 개수로 정의합니다. 그러면 구간을 한 칸 옮기는 것을 $O(1)$에 처리할 수 있습니다. $90\%$ 이상의 칸에서 $A_k$ 값이 일치해야 하는데, 이것은 어떻게 해야 할까요? 기존에 $B_i$가 최대인 $i$와 구간을 옮기면서 들어온 $A_k$를 확인해 준 다음, 후자의 $B_i$ 값이 더 크다면 전자를 갱신합니다. 이렇게 해서 $O(N)$에 문제를 해결할 수 있습니다. 난이도는 S2를 기여했습니다.

35097. 2025 (B4)

2026년의 41번째 문제입니다. $n$의 제한이 $100$으로 작기 때문에, 각 테스트 케이스마다 $O(n^2)$에 나이브하게 계산해 주면 됩니다. 난이도는 B4를 기여했습니다.

24751. Betting (B4)

2026년의 42번째 문제입니다. 첫 번째 줄에서는 $a:100=1:x$이므로 $x=\frac{100}{a}$입니다. 두 번째 줄에서는 $(100-a):100=1:x$이므로 $x=\frac{100}{100-a}$입니다. 난이도는 비례식이 초등학교 고학년 수준으로 알고 있어, 기여 가이드라인에 따라 B3를 기여했습니다.

34059. 2, 4, 6, 8 (B4)

2026년의 43번째 문제입니다. $42$는 조건을 만족합니다. 난이도는 B5를 기여했고, 절사당했습니다.

16727. ICPC (B4)

2026년의 44번째 문제입니다. 문제에서 요구하는 대로 case work를 해 주면 됩니다. 난이도는 B4를 기여했습니다.

1월 9일

34814. SCSC 동아리방 방문 (B2)

2026년의 45번째 문제입니다. 내일 shake! 오픈과 ABC가 모두 있으므로, 오늘 대회 셋을 돌기로 했습니다. 2025 SCSC 알고리즘 대난투에 출제된 문제를 풀기로 했고, #34813은 12월에 풀었기 때문에 #34814부터 풀게 되었습니다. 요구하는 대로 구현하면 되는 시뮬레이션 문제입니다. 난이도는 B2를 기여했습니다.

34815. $K+1$의 배수 (S3)

2026년의 46번째 문제입니다. $A_i$를 $K=i$일 때 답이 YES가 되기 위한 $N$의 최솟값으로 정의합시다. 그러면 $A_i=2\lfloor\frac{i+1}{2}\rfloor$입니다. $i$가 홀수일 때와 짝수일 때로 나누어 증명해 봅시다. $i$가 짝수라면, $\sum_{m=1}^im=\frac{i(i+1)}{2}$이 $i+1$의 배수이므로 $A_i=i$입니다.

$i$가 홀수라면, $\sum_{m=1}^im=\frac{i(i+1)}{2}$이 $i+1$의 배수가 되지 못합니다. $\sum_{m=1}^{I+1}m=\frac{(i+1)(i+2)}{2}$도 $i+1$의 배수가 아닙니다. $\sum_{m=1}^{i+1}m$의 나머지는 $[1,i]$에 속하므로 이들 중 하나를 제거하여, 즉 $i$개의 자연수를 선택하여 $i+1$의 배수를 만들 수 있습니다. 따라서 $A_i=i+1$입니다. 이를 하나로 모으면 $A_i=2\lfloor\frac{i+1}{2}\rfloor$가 됩니다. $N\ge{}A_k$이면 YES를, 그렇지 않으면 NO를 출력합니다. 난이도는 S3를 기여했습니다.

34816. 짝수 길이의 짝수 합 (G5)

2026년의 47번째 문제입니다. 길이가 $4$ 이상인 이진 문자열에서 부분 문자열 00, 11, 0101, 1010 중 하나 이상은 반드시 존재합니다. 이것들은 모두 짝수 길이의 짝수 합이므로, $y-x+1\ge4$이면 반드시 YES를 출력하면 됩니다. 00이나 11을 가지고 있을 때에도 YES를 출력해야 합니다. 그렇지 않은 경우에는 NO를 출력합니다. 난이도는 G4를 기여했습니다.

34817. 쉬운 정렬 문제 (G4)

2026년의 48번째 문제입니다. 두 원소를 교환할 수 있는 조건을 잘 생각해 보면 차이가 $K$ 초과인 두 원소는 작은 것이 앞에 있어야 한다고 볼 수 있습니다. 현재까지의 최댓값을 들고 있으면서 배열을 순회하면 $O(N)$에 가장 큰 inversion을 구할 수 있는데, 이 값이 $K$ 이하이면 정렬할 수 있습니다. 난이도는 G3를 기여했습니다.

27267. Сравнение комнат (B4)

2026년의 49번째 문제입니다. 성실하지 못한 @NeCu1029는 오늘도 '코딩시러'를 외치며 B4로 도망가 버렸습니다! $ab$와 $cd$를 비교해 주면 됩니다. 난이도는 B4를 기여했습니다.

1월 10일

28648. Торговый центр (B4)

2026년의 50번째 문제입니다. 오늘은 shake! 오픈과 ABC가 모두 있기 때문에, 14시부터는 대회에 매진해야 합니다. 따라서 B4 5개만 밀고 대회를 치기로 했습니다. $t_i+l_i$의 최솟값을 구하면 되는 간단한 문제입니다. 난이도는 B4를 기여했습니다.

26772. Poziome serca (B4)

2026년의 51번째 문제입니다. 하트 모양을 가로로 출력하는 문제인데, 각 줄마다 배열에 저장하여 반복 출력해 주면 됩니다. 공백에 유의해 줍시다. 난이도는 B5를 기여했습니다.

25858. Divide the Cash (B4)

2026년의 52번째 문제입니다. $i$번째 사람이 푼 문제 수를 $A_i$, 푼 문제 수의 총합을 $S$라 할 때, $\frac{dA_i}{S}$를 모두 출력하면 됩니다. 난이도는 B3를 기여했습니다.

34935. 오름차순과 비내림차순 (B4)

2026년의 53번째 문제입니다. 수열 $A$가 있을 때, 임의의 인접한 두 원소 $A_i$, $A_{i+1}$에 대해 $A_i<A_{i+1}$이면 오름차순, $A_i\le{}A_{i+1}$이면 비내림차순입니다. 따라서 $A_i=A_{i+1}$인 경우가 있는지 없는지 검사하면 됩니다. 난이도는 B4를 기여했습니다.

34824. 연대 다음 고대 (B4)

2026년의 54번째 문제입니다. yonsei와 korea 중 무엇이 먼저 입력되는지 봐 주면 됩니다. 난이도는 B5를 기여했습니다.

35106. 릴레이 가위바위보 게임 (B3)

35107. 히든 이벤트 (S2)

35112. 으악그래프 (G5)

35115. i18n (G2)

2026년의 55~58번째 문제들입니다. 이 글을 참고해 주세요.

1월 11일

28069. 김밥천국의 계단 (G5)

2026년의 59번째 문제입니다. 어제 건실하지 못한 B4 밀기를 했기 때문에, 오늘은 건실하게 G5부터 업다운 랜디를 하고자 합니다. 문제에는 "정확히 $K$번째" 행동에서 $N$번째 계단에 도달해야 한다고 되어 있지만, 사실은 그럴 필요가 없습니다. $0$번째 계단에서 지팡이를 아무리 많이 두드려도 위치가 변하지 않기 때문에, $K$번 이하의 횟수로 $N$번째 계단에 도달하기만 해도 되죠. 이제 BFS로 $N$번째 계단에 도달하는 최소 횟수를 찾으면 됩니다. 난이도는 G5를 기여했습니다.

17281. ⚾ (G4)

2026년의 60번째 문제입니다. 선수의 타순을 정하는 문제인데, 1번 선수가 4번 타자가 아닌 경우를 배제하면 $8!<10^5$이므로 모든 경우의 수를 시도해 볼 수 있습니다. 각 타순의 점수도 마찬가지로 시뮬레이션으로 알아내면 됩니다... 라고 간단하게 썼지만, 구현이 매우 더럽습니다. 난이도는 G3를 기여했습니다.

14718. 용감한 용사 진수 (G4)

2026년의 61번째 문제입니다. G3 문제를 뽑았지만, #17281보다도 어려운 구현에 포기하여 다시 G4로 돌아왔습니다. 뭔가 DP를 써야 할 것처럼 생겼지만, $N$ 제한이 $100$에 불과하다는 것을 생각해 봅시다. $K$명 이상의 병사를 이기기 위한 진수의 최소 스탯은 능력치 종류별로 각각 하나 이상의 병사와 같을 것입니다. 즉 $N^3$가지 스탯만 확인해 보면 되고, 각 스탯을 판정하는 데 $O(N)$이 걸립니다. 전체 시간 복잡도는 $O(N^4)$이지만, 연산이 단순하기 때문에 넉넉하게 통과합니다. 난이도는 G5를 기여했습니다.

1222. 홍준 프로그래밍 대회 (G2)

2026년의 62번째 문제입니다. 여기서부터는 업다운 랜디가 아닙니다. Goodbye, BOJ! 2025의 B번을 대회 중에 풀지 못했는데, 조화수를 이용해 $O(N\log{N})$에 문제를 해결하는 유형이었습니다. 이러한 유형을 익히고자 조화수 문제 2개를 더 풀기로 했습니다.

홍준이가 설정할 수 있는 인원 수는 최대 $2~000~000$입니다. 따라서 인원 수가 $1$일 때부터 $2~000~000$일 때까지 가능한 팀 수를 모두 확인해 봅시다. $M=2~000~000$이라 할 때, 길이 $M$의 배열 $A$를 만들어 $A_i$에 학생 수가 $i$인 학교 수를 저장합니다. 이제 팀별 인원 수 $x$에 대해 $M$ 이하의 $x$의 배수만 확인하면 되므로, $O(M\log{M})$에 문제를 해결할 수 있습니다. 난이도는 G2를 기여했습니다.

23820. MEX (G2)

2026년의 63번째 문제입니다. 이번 문제도 조화수를 이용합니다. $2~000~003$은 소수이며, 문제에 주어진 $a_i$의 제한보다 큽니다. 따라서 이 수는 절대 $a_i\times{}a_j$로 표현할 수 없으며, 문제의 정답은 $2~000~003$을 초과할 수 없습니다. 따라서 입력 배열에서 중복을 제거하고 정렬해 준 뒤, $a_i\times{}a_j\le{}2~000~003$인 경우만 확인해 줍시다. 여기에 #1222의 방법을 적용해 준다면 $M=2~000~003$이라 할 때 $O(M\log{M})$에 문제를 해결할 수 있습니다. 난이도는 G1을 기여했습니다.

1월 12일

34980. 생수병 놓기 (B3)

2026년의 64번째 문제입니다. 오늘은 별조각 쌀먹을 위해 랜덤 마라톤을 돌 생각입니다. 두 경우 각각에서 생수병의 개수, 그리고 변경된 배치가 있는지 여부를 관리해 주며 조건 분기를 하면 됩니다. 난이도는 B3를 기여했습니다.

3076. 상근이의 체스판 (B2)

2026년의 65번째 문제입니다. 별 찍기처럼 적당히 출력해 주면 됩니다. 난이도는 B3를 기여했습니다.

3041. N-퍼즐 (B1)

2026년의 66번째 문제입니다. 각 알파벳마다 원래 위치와의 맨해튼 거리를 직접 계산해 주면 됩니다. 난이도는 B1을 기여했습니다.

13301. 타일 장식물 (S5)

2026년의 67번째 문제입니다. $i$번째 피보나치 수를 $F_i$라 할 때, 답은 $2(F_N+F_{N+1})=2F_{N+2}$입니다. 난이도는 S5를 기여했습니다.

2910. 빈도 정렬 (S3)

2026년의 68번째 문제입니다. 배열을 입력받으면서 각 수의 빈도와 처음 등장하는 위치를 각각 해시맵이나 트리맵에 저장해 줍니다. 이제 이것을 기준으로 하여 정렬하면 됩니다. 난이도는 S4를 기여했습니다.

1월 13일

17903. Counting Clauses (B4)

2026년의 69번째 문제입니다. 현생 이슈로 B4 날먹을 선택했습니다. 지문이 매우 긴 데다 한국어가 아니어서 해석에 어려움이 있지만, 사실 3-SAT을 몰라도 해결할 수 있습니다. 처음 들어오는 절의 개수 $m$이 $8$ 이상인지만 확인하면 됩니다. 난이도는 B5를 기여했습니다.

30156. Malvika is peculiar about color of balloons (B4)

2026년의 70번째 문제입니다. 색 반전을 해야 하는 최소한의 풍선 수는 각 색의 풍선 수 중 더 적은 것과 같습니다. 난이도는 B4를 기여했습니다.

31282. ЛОВНО КУЧЕ (B4)

2026년의 71번째 문제입니다. $\lceil\frac{N}{K-M}\rceil$을 출력하면 됩니다. 난이도는 B4를 기여했습니다.

34346. 대각선 (B4)

2026년의 72번째 문제입니다. $N$이 홀수이면 답은 $1$, 짝수이면 답은 $2$입니다. 난이도는 B4를 기여했습니다.

33163. OIJ (OIJ) (B4)

2026년의 73번째 문제입니다. 문제에서 요구하는 대로 구현해 주면 됩니다. 난이도는 B4를 기여했습니다.

1월 14일

11066. 파일 합치기 (G3)

2026년의 74번째 문제입니다. 오늘은 DP를 밀기로 했습니다. 편의를 위해 $i$번째 장의 크기를 $A_i$라 하겠습니다. 먼저 파일 크기에 누적 합을 적용합니다. 이제 $DP[i][j]$를 $i$번째 장부터 $j$번째 장까지 합치는 최소 비용으로 정의합니다. 초깃값은 $DP[i][i]=0$, $DP[i][i+1]=A_i+A_{i+1}$입니다. 점화식은 $DP[i][j]=\min_{m=i}^{j-1}(DP[i][m]+DP[m+1][j])+(A_i+A_{i+1}+\cdots+A_j)$입니다. 난이도는 G2를 기여했지만, 난이도 표준 문제라 반영되지 않았습니다.

1937. 욕심쟁이 판다 (G3)

2026년의 75번째 문제입니다. 한 칸에서 다른 칸으로 이동할 수 있는 관계를 그래프로 나타내면 DAG가 됩니다. 따라서 $DP[i][j]$를 $(i,j)$에서 시작하여 이동할 수 있는 칸 수의 최댓값으로 하고, DFS를 돌면서 테이블을 채워 나가면 됩니다. 난이도는 G3를 기여했습니다.

15990. 1, 2, 3 더하기 5 (S1)

2026년의 76번째 문제입니다. $DP[i][j]$를 마지막에 $j$를 더해 $i$에 도달하는 경우의 수로 정의합니다. $i=3$까지 하드코딩을 해준 뒤, 점화식 $DP[i][j]=DP[i-j][1]+DP[i-j][2]+DP[i-j][3]-DP[i-j][j]$를 이용합니다. $i=100000$까지 DP 테이블을 모두 채워주고, 테스트 케이스마다 답을 출력하면 됩니다. 난이도는 S1을 기여했습니다.

15989. 1, 2, 3 더하기 4 (G5)

2026년의 77번쨰 문제입니다. 1, 2, 3 더하기 5를 풀었는데, 4를 아직 안 풀어서 풀기로 했습니다. 수의 순서만 다른 것은 같은 경우로 센다고 하는데, 이는 이전에 더한 수보다 크거나 같은 수만 더할 수 있는 것과 동치입니다. 이를 이용하여 DP 테이블을 잘 채우면 됩니다. 정의는 #15990과 동일하고, 점화식만 바뀝니다. 난이도는 S1을 기여했습니다.

1351. 무한 수열 (G5)

2026년의 78번째 문제입니다. 문제에서 점화식을 제공합니다! 탑다운 DP를 사용해 그대로 구현해 주면 됩니다. 길이 $10^{12}$의 배열을 만들면 MLE가 나지만, $N$이 줄어드는 속도가 매우 빠르므로 $10^6$ 정도만 메모이제이션 해주어도 AC를 받을 수 있습니다. 난이도는 S2를 기여했고, 절사당했습니다.

21553. 암호 만들기 (B3)

2026년의 79번째 문제입니다. 랜덤 마라톤 A입니다. 뭔가 복잡해 보이지만, 생각을 잘 해보면 매우 쉬운 문제입니다. $B$의 길이에 대한 조건이 없기 때문에, $P$를 그대로 출력하면 됩니다! 난이도는 B3를 기여했습니다.

1월 15일

1940. 주몽 (S4)

2026년의 80번째 문제입니다. 나이브한 방법으로는 $O(N^2)$이 들지만, 정렬과 투 포인터를 사용해 $O(N\log{}N)$에 해결할 수 있습니다. 먼저 재료 번호 배열을 정렬해 주고, 두 개의 포인터를 각각 배열의 시작과 끝에 놓습니다. 그 후 현재 두 포인터가 보고 있는 값의 합이 $M$보다 작으면 앞 포인터를 오른쪽으로 옮기고, 그렇지 않으면 뒤 포인터를 왼쪽으로 옮겨 두 포인터의 위치가 같아질 때까지 반복합니다. 난이도는 S4를 기여했습니다.

15688. 수 정렬하기 5 (S5)

2026년의 81번째 문제입니다. 시간 누적이라고 해서 뭔가 달라 보이지만, 적당히 빠른 입출력과 적당히 빠른 정렬을 사용하면 통과할 수 있습니다. 난이도는 S5를 기여했습니다.

20040. 사이클 게임 (G4)

2026년의 82번째 문제입니다. Union-Find를 사용합니다. 새로 연결된 두 정점에 Union 연산을 수행하는 것을 반복하다가, 같은 집합에 속하는 두 정점을 Union하게 될 때 사이클이 생긴다고 판정하면 됩니다. 난이도는 G4를 기여했지만, 난이도 표준이기 때문에 큰 의미는 없습니다.

10203. Count Vowels (B4)

2026년의 83번째 문제입니다. 말 그대로 모음의 개수를 세어 주면 됩니다. 난이도는 B4를 기여했습니다.

32288. 바코드 닉네임 (B4)

2026년의 84번째 문제입니다. l이 들어오면 L을, I가 들어오면 i를 출력하면 됩니다. 난이도는 B5를 기여했습니다.

1월 16일

25421. 조건에 맞는 정수의 개수 (S1)

2026년의 85번째 문제입니다. $DP[i][j]$를 조건을 만족하는 $i$자리 자연수 중 일의 자리가 $j$인 것의 개수로 정의합니다. $j$의 뒤에는 $j-2$부터 $j+2$까지의 숫자를 붙일 수 있다는 것을 이용하면 쉽게 DP 점화식을 세울 수 있습니다. 사용할 수 있는 숫자에서 $0$은 제외됨에 유의합시다. 시간 복잡도는 S1을 기여했습니다.

16936. 나3곱2 (G5)

2026년의 86번째 문제입니다. 먼저 정답이 유일하다는 데 주목해 줍시다. 어떤 수에서 $2$가 곱해진 횟수와 $3$이 곱해진 횟수를 각각 $a$, $b$라고 했을 때, 정답 수열에서 $a-b$가 반드시 $1$씩 증가하기 때문입니다. 따라서 각 수에 대해 $a-b$값을 구하고, 이 값이 최소인 것부터 쭉 나열하면 됩니다. 난이도는 G5를 기여했습니다.

10973. 이전 순열 (S3)

2026년의 87번째 문제입니다. C++에서는 next_permutation으로 다음 순열을 구할 수 있습니다. 이때, 순열의 모든 원소를 부호 반전하여 구한 다음 순열은 처음 순열의 이전 순열을 부호 반전한 것과 같습니다. 기여 창을 보니 아예 prev_permutation이라는 함수도 있다고 합니다. 난이도는 함수를 알면 딸깍이라는 점에서 B5를... 기여할 수는 없으니 S4를 기여했습니다.

25494. 단순한 문제 (Small) (B4)

2026년의 88번째 문제입니다. 모든 경우를 테스트해 보면 됩니다. 시간 복잡도는 $O(Tabc)$입니다. 난이도는 B3를 기여했습니다.

29736. 브실이와 친구가 되고 싶어 🤸‍♀️ (B4)

2026년의 89번째 문제입니다. 간단한 수학을 사용해도 되고, 브루트 포스를 해도 무방합니다. 난이도는 B4를 기여했습니다.

1월 17일

7579. 앱 (G3)

2026년의 90번째 문제입니다. $DP[i][j]$를 $i$번째 앱까지 활용했을 때, 비용 $j$ 이내로 확보할 수 있는 최대 메모리로 정의합시다. 초깃값은 $DP[0][j]=0$입니다. 이제 점화식을 세워 봅시다. $DP[i][j]$는 다음 값들 중 최댓값과 같습니다.

• $DP[i-1][j]$
• ($j\ge{}c_i$일 경우) $DP[i-1][j-c_i]+m_i$

이를 구현한 뒤, $DP[N][j]\ge{}M$을 만족하는 최소의 $j$를 출력하면 AC를 받을 수 있습니다. 시간 복잡도는 $O(N\sum_{i=1}^Nc_i)$입니다. 난이도 표준이기 때문에 기여의 의미는 없지만, 난이도는 G3를 기여했습니다.

15486. 퇴사 2 (G5)

2026년의 91번째 문제입니다. $DP[i]$를 $i$일 이전에 잡은 상담 중 $i$일까지 이어지는 것이 없을 때, $i$일부터 $N$일까지 얻을 수 있는 최대 수익으로 정의합시다. 초깃값은 $DP[N+1]=0$입니다. 이제 점화식을 세워 봅시다. $DP[i]$는 다음 값들 중 최댓값과 같습니다.

• $DP[i+1]$
• ($i+T_i\le{}N+1$일 경우) $DP[i+T_i]+P_i$

DP 테이블을 $DP[N]$부터 거꾸로 채워 나가면 $DP[1]$이 답이 됩니다. 난이도는 S1을 기여했습니다.

2011. 암호코드 (G5)

2026년의 92번째 문제입니다. 먼저 문자열의 첫 번째 글자가 0이라면, 이것을 만족하는 해석이 없으므로 답은 $0$입니다. 그렇지 않다면, $DP[i]$를 첫 번째 글자부터 $i$번째 글자까지의 부분 문자열로 만들 수 있는 해석의 가짓수를 $10^6$으로 나눈 나머지로 정의합시다. 초깃값은 $DP[0]=DP[1]=1$입니다. 이제 점화식을 세워 봅시다. $DP[i]$는 다음 값들의 합을 $10^6$으로 나눈 나머지와 같습니다.

• ($i$번째 글자가 0이 아닐 경우) $DP[i-1]$
• ($i-1$번째 글자와 $i$번째 글자를 합쳐 $10$ 이상 $26$ 이하의 자연수를 만들 수 있을 경우) $DP[i-2]$

DP 테이블을 $DP[2]$부터 모두 채우면 마지막 값이 답이 됩니다. 난이도는 G5를 기여했습니다.

5582. 공통 부분 문자열 (G5)

2026년의 93번째 문제입니다. 두 문자열을 각각 $S$, $T$라 할 때, $DP[i][j]$를 $S_i$와 $T_j$를 각각 끝으로 하는 최장 공통 부분 문자열의 길이로 정의합시다. 초깃값은 $DP[i][0]=0,DP[0][j]=0$입니다. 이제 점화식을 세워 봅시다. $DP[i][j]$의 값은 다음과 같습니다.

• $S_i=T_j$인 경우, $DP[i-1][j-1]+1$
• $S_i\ne{}T_j$인 경우, $0$

DP 테이블을 모두 채우면, 전체 테이블에서의 최댓값이 답이 됩니다. 난이도는 G5를 기여했습니다.

2491. 수열 (S4)

2026년의 94번째 문제입니다. LIS와 유사해 보이지만, 부분 수열이 연속이어야 한다는 차이가 있습니다. 따라서 $DP_1[i]$를 $i$번째 원소로 끝나는 최장 연속 단조증가 수열의 길이로 정의합시다. 초깃값은 $DP_1[1]=1$입니다. 이제 점화식을 세워 봅시다. $DP_1[i]$의 값은 다음과 같습니다.

• $A_{i-1}\le{}A_i$일 경우, $DP_1[i-1]+1$
• $A_{i-1}>A_i$일 경우, $1$

같은 방법으로 $DP_2[i]$를 $i$번째 원소로 끝나는 최장 연속 단조감소 수열의 길이로 정의하고, 점화식을 적절히 세웁니다. 이제 $DP_1$과 $DP_2$ 모두에서 전체 최댓값이 답이 됩니다. 난이도는 S4를 기여했습니다.

1695. 팰린드롬 만들기 (G3)

2026년의 95번째 문제입니다. $DP[i][j]$를 $i$번째부터 $j$번째 수까지의 부분 수열에서 문제의 정답으로 정의합시다. 초깃값은 $i\ge{}j$일 때 $DP[i][j]=0$입니다. 이제 점화식을 세워 봅시다. $DP[i][j]$의 값은 다음과 같습니다.

• $A_i=A_j$일 경우, $DP[i+1][j-1]$
• $A_i\ne{}A_j$일 경우, $\min(DP[i+1][j],DP[i][j-1])+1$

탑다운 DP를 사용하는 것이 더 간단합니다. 난이도는 G3를 기여했습니다.

1월 18일

16199. 나이 계산하기 (B4)

2026년의 96번째 문제입니다. 현재 연도에서 생년을 뺀 값을 $x$라 합시다. 그러면 만 나이, 세는 나이, 연 나이는 각각 다음과 같습니다.

• 만 나이: 생일이 지났다면 $x$, 그렇지 않다면 $x-1$
• 세는 나이: $x+1$
• 연 나이: $x$

이를 그대로 구현하면 AC를 받을 수 있습니다. 난이도는 B3를 기여했습니다.

24724. 현대모비스와 함께하는 부품 관리 (B4)

2026년의 97번째 문제입니다. 문제가 매우 복잡해 보이지만, 사실 아래 문장을 $x$ 자리의 수만 바꾸어 $T$회 출력하면 됩니다.

Material Management x
Classification ---- End!

난이도는 B5를 기여했습니다.

28940. Дневник Гравити Фолз (B4)

2026년의 98번째 문제입니다. $\lceil\frac{n}{\lfloor\frac{w}{a}\rfloor\lfloor\frac{h}{b}\rfloor}\rceil$를 출력하되, $\lfloor\frac{w}{a}\rfloor\lfloor\frac{h}{b}\rfloor=0$이면 -1을 출력합니다. 난이도는 B4를 기여했습니다.

30979. 유치원생 파댕이 돌보기 (B4)

2026년의 99번째 문제입니다. 사탕의 맛의 합을 구해 파댕이를 돌봐야 하는 시간과 비교하면 됩니다. 난이도는 B4를 기여했습니다.

30031. 지폐 세기 (B4)

2026년의 100번째 문제입니다. 지폐의 가로 길이에 따라 액수를 구하고, 모두 더해주면 됩니다. 난이도는 B4를 기여했습니다.

1월 19일

14891. 톱니바퀴 (G5)

2026년의 101번째 문제입니다. 네 톱니바퀴의 회전 상태를 덱으로 관리해 줍니다. 입력에서 주어진 톱니바퀴가 회전하면, 주위 톱니바퀴를 봐 주면서 함께 회전해야 하는지 판별합니다. 회전은 덱의 한쪽에서 pop한 것을 반대쪽에 push하는 방식으로 진행합니다. 이것을 반복한 뒤 최종 상태를 출력해 주면 됩니다. 난이도는 G4를 기여했습니다.

1111. IQ Test (G3)

2026년의 102번째 문제입니다. 조건을 나누어 생각해 봅시다.

• $N=1$일 경우: 답은 반드시 A입니다.
• $N=2$일 경우: 배열의 두 수가 같다면 그 수가 답이고, 그렇지 않다면 답은 A입니다.
• $N>2$일 경우: 배열의 $i$번째 수를 $A_i$라 할 때, 모든 점 $(A_i,A_{i+1})$는 한 직선 위에 있습니다. 따라서 $A_1$부터 $A_3$까지의 수를 이용해 직선을 찾아 주고, 이 직선 위에 모든 점이 있는지 검사하면 됩니다.

위를 그대로 구현하면 AC를 받습니다. 난이도는 G3를 기여했습니다.

15662. 톱니바퀴 (2) (G5)

2026년의 103번째 문제입니다. #14891에서 톱니바퀴의 개수만 늘어난 문제입니다. 이미 덱을 사용하여 충분히 최적화하였으므로 조금만 수정해 줍니다. 난이도는 G4를 기여했습니다.

34323. 할인이 필요해 (B4)

2026년의 104번째 문제입니다. 상품 $M+1$개를 구매하는 데 $M+1$ 할인은 $MS$, $N\%$ 할인은 $\frac{100-N}{100}(M+1)S$의 비용이 듭니다. 이 둘을 비교하여 더 유리한 금액을 출력해 줍시다. 난이도는 B5를 기여했습니다.

34823. YCPC 점수 (B4)

2026년의 105번째 문제입니다. YCPC는 Y 1개, C 2개, P 1개로 만들 수 있습니다. 난이도는 B5를 기여했습니다.

1월 20일

16724. 피리 부는 사나이 (G3)

2026년의 106번째 문제입니다. 격자 밖으로 나가는 경우가 없으므로, 사이클의 개수를 세어 주면 됩니다. 이때 DFS를 활용해 줍니다. 태그에 분리 집합이 있지만, DFS를 사용한다면 딱히 필요 없습니다. 물론 DFS 없이 분리 집합만으로 풀 수도 있습니다. 난이도는 G3를 기여했습니다.

28065. SW 수열 구하기 (S4)

2026년의 107번째 문제입니다. $1$에서 시작하여 $N-1$을 더하고, $N-2$를 빼고, ...를 반복하면 됩니다. 난이도는 S4를 기여했습니다.

14867. 물통 (G2)

2026년의 108번째 문제입니다. 전혀 그래 보이지 않지만, 그냥 BFS를 돌리면 됩니다. $1$개 이상의 단계를 거치면 두 물통 중 적어도 하나는 완전히 비거나 완전히 차므로, 가능한 상태가 $O(a+b)$에 bound됩니다. 다만 공간 복잡도를 해결하기 위해 방문 처리를 맵으로 해 줍시다. 난이도는 G3를 기여했습니다.

12850. 본대 산책2 (P5)

2026년의 109번째 문제입니다. 그래프의 인접 행렬 $A$에 대하여, $A^D$의 $P$행 $Q$열은 $P$번 정점에서 $Q$번 정점으로 $D$개의 길을 거쳐 가는 경우의 수와 같습니다. $D$의 제한이 매우 크므로 분할 정복을 이용해 줍시다. 난이도는 P5를 기여했습니다.

31822. 재수강 (B4)

2026년의 110번째 문제입니다. 문자열의 앞 5자리를 직접 비교해 주면 되는 단순한 문제입니다. 난이도는 B4를 기여했습니다.

1월 21일

2688. 줄어들지 않아 (S1)

2026년의 111번째 문제입니다. $DP[i][j]$를 일의 자리 수가 $j$인 줄어들지 않는 $i$자리 수의 개수로 정의합시다. 초깃값은 $DP[1][j]=1$입니다. 이제 점화식을 세워 봅시다. $DP[i][j]=\sum_{k=0}^jDP[i-1][k]$입니다. 배열 $DP[i-1]$에 누적 합을 적용하면 $DP[i]$가 되는 것으로도 이해할 수 있습니다. 가능한 $n$의 범위까지 DP 테이블을 돌린 뒤, 쿼리가 들어올 때마다 꺼내서 반환합시다. 답은 $DP[n+1][9]$와 같습니다. 난이도는 S1을 기여했습니다.

34967. 최대공약수 완충재 (P5)

2026년의 112번째 문제입니다. $1\times19999$, $1\times19998$, $2\times19998$, $2\times19997$, ...을 쭉 출력해 줍시다. $10000\times10000$까지 출력하면 $19999$개의 정수를 출력하게 되는데, $N=20000$일 때 $10^8$을 한 번 더 출력해 주면 AC를 받을 수 있습니다. 난이도는 G1을 기여했습니다.

33622. 새치기하지 마!!! (S5)

2026년의 113번째 문제입니다. 재우가 어떻게 새치기를 하든, 끝까지 잡히지 않을 확률은 $\frac{1}{n+1}$로 동일합니다. 따라서 아무렇게나 출력해 줍시다. 난이도는 S5를 기여했습니다.

2912. 백설공주와 난쟁이 (P2)

2026년의 114번째 문제입니다. 입력받은 범위에서 랜덤으로 모자 색을 고르고 인덱스 배열의 이분 탐색으로 과반인지 확인합니다. 만약 문제의 답이 no라면 항상 과반이 아닐 것이고, yes라면 절반 이상의 확률로 고른 원소가 과반일 것입니다. 따라서 이 작업을 여러 번 반복해 줍시다. 난이도는 P2를 기여했습니다.

27865. 랜덤 게임? (B1)

2026년의 115번째 문제입니다. 답이 Y일 때까지 ? 1을 쭉 반복하면 충분히 높은 확률로 AC를 받습니다. 난이도는 B2를 기여했습니다.

1월 22일

11662. 민호와 강호 (G4)

2026년의 116번째 문제입니다. 시간 $1$에 민호와 강호가 목적지에 도착한다고 할 때, 시간 $t$에 둘 사이 거리를 $f(t)$라 하면 $f$는 유니모달한 함수입니다. 증명은 생략합니다. 따라서 삼분 탐색을 통해 최솟값을 찾아줄 수 있습니다. 난이도는 G4를 기여했습니다.

30794. 가희와 클럽 오디션 1 (B4)

2026년의 117번째 문제입니다. 지문이 매우 길지만 모두 페이크이고, 판정에 따라 결정되는 정수에 $lv$를 곱하면 됩니다. 난이도는 B4를 기여했습니다.

29267. Случай с игрой (B4)

2026년의 118번째 문제입니다. 문제에서 주어진 대로 행동하면 됩니다. 난이도는 B4를 기여했습니다.

29097. Короли (B4)

2026년의 119번째 문제입니다. Joffrey, Robb, Stannis가 갖고 있는 병사의 수는 각각 $na$, $mb$, $kc$입니다. 이 값들이 최댓값과 같은 모든 사람을 출력합시다. 난이도는 B5를 기여했고, 절사당했습니다.

34449. King Arthur's Round Table (B4)

2026년의 120번째 문제입니다. $\pi{}d$와 $wn$을 비교해 줍시다. 난이도는 B3를 기여했고, 절사당했습니다.

1월 23일

16938. 캠프 준비 (G5)

2026년의 121번째 문제입니다. $N\le15$이므로 $O(2^N)$과 $O(2^NN)$이 모두 가능합니다. 따라서 가능한 모든 경우의 수를 직접 테스트하는 브루트 포스로 해결해 줍시다. 난이도는 S1을 기여했습니다.

2022. 사다리 (G4)

2026년의 122번째 문제입니다. 건물 사이의 너비가 정해져 있을 때, 교점의 높이는 쉽게 구할 수 있습니다. 또한 건물 사이의 너비가 증가하면 교점의 높이는 감소합니다. 따라서 이분 탐색을 통해 오차 범위 내로 답을 구해 줍시다. 난이도는 G3를 기여했습니다.

1756. 피자 굽기 (G5)

2026년의 123번째 문제입니다. 오븐 배열의 $i$번째 값을 $A_i$라고 할 때, $i<j$라면 $A_i<A_j$인 것과 $A_i=A_j$이 다르지 않습니다 반지름이 $A_i$보다 큰 피자는 어차피 더 깊이 들어올 수 없기 때문이죠. 이를 이용해 배열을 비오름차순으로 변형한 뒤, 깊은 곳부터 탐색해 줍시다. 난이도는 G4를 기여했습니다.

29823. Pakirobot Manhattanis (B4)

2026년의 124번째 문제입니다. 문제에서 주어진 대로 이동한 다음, 최종 위치와 출발지 사이의 맨해튼 거리를 구해 주면 됩니다. 난이도는 B4를 기여했습니다.

33179. Hezardastan’s Annual Report (B4)

2026년의 125번째 문제입니다. 각각의 수 $n$마다 $\lfloor\frac{n+1}{2}\rfloor$를 더해 출력해 줍시다. 난이도는 B4를 기여했습니다.

1월 24일

2602. 돌다리 건너기 (G4)

2026년의 126번째 문제입니다. $DP[i][j][k]$를 $i$번째 다리의 $j$번 칸을 도착지로 하여 목표 문자열을 $k$번째 글자까지 만들 수 있게 하는 경우의 수로 정의합니다. $i$는 $0$ 또는 $1$입니다. 초깃값은 $DP[0][0][0]=DP[1][0][0]=1$입니다. 이제 점화식을 세워 봅시다.

• $i$번째 다리의 $j$번 칸에 적힌 문자가 목표 문자열의 $k$번째 문자와 다른 경우, $DP[i][j][k]=0$
• $i$번째 다리의 $j$번 칸에 적힌 문자가 목표 문자열의 $k$번째 문자와 같은 경우, $DP[i][j][k]=\sum_{x=0}^{j-1}DP[1-i][x][k-1]$

답은 $k$가 목표 문자열의 길이와 같은 경우의 DP값을 모두 더한 것입니다. 난이도는 G4를 기여했습니다.

14908. 구두 수선공 (G1)

2026년의 127번째 문제입니다. $T$가 작고 $S$가 클수록 먼저 처리하는 것이 좋음은 자명합니다. 그래서 $\frac{T}{S}$의 오름차순으로 정렬하는 것을 생각해 보았고, Proof by AC했습니다. 증명은 인터넷을 참고했고, 난이도는 P5를 기여했습니다.

2036. 수열의 점수 (G4)

2026년의 128번째 문제입니다. 먼저 주어진 수에 양수만 있는 경우를 생각해 봅시다. 이때는 큰 수부터 차례로 곱해 주는 것이 최선입니다. 그러다 $1$이 나오면, $1$은 따로 더해 주어야 점수를 높일 수 있습니다. 여기에 $0$과 음수까지 포함된다면, 음수는 절댓값이 큰 것부터 차례로 곱해 양수로 만들고, 혼자 남은 음수가 있다면 $0$과 함께 제거하거나 ($0$이 있을 경우) 따로 제거하면 됩니다. 난이도는 G4를 기여했습니다.

2600. 구슬게임 (G4)

2026년의 129번째 문제입니다. 두 통에 담긴 구슬의 개수가 각각 $i$, $j$일 때 선공이 승리한다면 $0$, 후공이 승리한다면 $1$을 $DP[i][j]$에 담아 줍니다. 이 값이 정의되는 경우를 유효하다고 합시다. 그러면 DP 테이블을 채우는 규칙은 다음과 같습니다.

• $DP[i-b_1][j]$, $DP[i-b_2][j]$, $DP[i-b_3][j]$, $DP[i][j-b_1]$, $DP[i][j-b_2]$, $DP[i][j-b_3]$ 중 유효하고 그 값이 $1$인 것이 존재한다면 $DP[i][j]=0$
• 그렇지 않다면 $DP[i][j]=1$

이 규칙대로 DP 테이블을 모두 채워준 다음 입력으로 들어오는 질문에 맞춰 답을 내면 됩니다. 난이도는 G4를 기여했습니다.

11695. 표 게임 (P4)

2026년의 130번째 문제입니다. 각 행을 하나의 님 게임 돌무더기로 볼 수 있습니다. 돌의 개수는 행에 있는 모든 수의 합입니다. 돌의 개수를 XOR 하여 답을 구해 줍시다. 난이도는 P4를 기여했습니다.

1월 25일

14921. 용액 합성하기 (G5)

2026년의 131번째 문제입니다. 간단한 투 포인터 문제입니다. 처음 위치는 맨 앞과 맨 뒤로 하고, 혼합 용액의 특성값이 음수라면 왼쪽 것을, 양수라면 오른쪽 것을 옮겨 줍시다. $0$이라면 그것이 그대로 답이 됩니다.

2410. 2의 멱수의 합 (G5)

2026년의 132번째 문제입니다. $DP[i]$를 $N=i$일 때의 답으로 정의합니다. 초깃값은 $DP[0]=1$입니다. 이제 점화식을 세워 봅시다. $i\ge1$일 때, $DP[i]$의 값은 다음과 같습니다.

• $i$가 홀수일 경우: $DP[i-1]$ ($N=i-1$일 때의 경우에서 $+1$을 추가하는 것)
• $i$가 짝수일 경우: $DP[i-1]+DP[\frac{i}{2}]$ ($N=i-1$일 때의 경우에서 $+1$을 추가, 또는 $N=\frac{i}{2}$일 떄의 경우에서 각 수에 $2$를 곱합)

이것을 구현한 뒤 $DP[N]$을 출력하면 답이 됩니다.

16194. 카드 구매하기 2 (S1)

2026년의 133번째 문제입니다. $DP[i]$를 $i$장의 카드를 사는 최소 비용으로 정의합니다. 초깃값은 $DP[0]=0$입니다. 이제 점화식을 세워 봅시다. $i\ge1$일 때, $DP[i]$는 다음 중 최솟값과 같습니다.

• $DP[i-1]+P_1$
• $i\ge2$일 경우, $DP[i-2]+P_2$
  $\cdots$
• $i\ge{}N$일 경우, $DP[i-N]+P_N$

이를 통해 DP 테이블을 채운 뒤, $DP[N]$을 출력하면 답이 됩니다.

9613. GCD 합 (S4)

2026년의 134번째 문제입니다. 브루트 포스를 통해 모든 쌍을 직접 계산해 줍시다.

2851. 슈퍼 마리오 (B1)

2026년의 135번째 문제입니다. 수를 쭉 읽다가, 10개를 모두 읽었거나 합이 $100$ 이상이 되는 경우 중단합니다. 그 뒤 지금까지 계산한 합들 중 $100$에 가장 가까운 것을 출력합니다.

1월 26일

14677. 병약한 윤호 (G5)

2026년의 136번째 문제입니다. 각 약마다 $1$번부터 $3N$번까지 번호를 붙입시다. 그 다음 남아있는 약 번호 중 최솟값 $l$, 최댓값 $r$을 한 쌍으로 묶어 $(l,r)$ 형태로 관리해 줍니다. $r-l$을 $3$으로 나눈 나머지를 통해 현재 먹어야 하는 약의 종류를 쉽게 알 수 있습니다. 이제 그래프 탐색을 통해 가능한 $3N-r+l-1$의 최댓값을 찾습니다. 난이도는 G4를 기여했습니다.

34073. DORO (B4)

2026년의 137번째 문제입니다. 각 단어를 공백으로 구분하여 입력받아 주면서, 입력받은 그대로에 DORO 를 덧붙이면 되는 단순한 문제입니다. 난이도는 B5를 기여했습니다.

32089. 部員の変遷 (B4)

2026년의 138번째 문제입니다. 연속된 길이 $3$의 부분 수열 중 합의 최댓값을 찾아 출력해 줍시다. 난이도는 B4를 기여했습니다.

34400. 민규의 서카디안 리듬 (B4)

2026년의 139번째 문제입니다. $t$를 $25$로 나눈 나머지에 따라 판정해 주면 됩니다. 난이도는 B4를 기여했습니다.

34750. 추석은 언제나 좋아 (B4)

2026년의 140번째 문제입니다. 문제에서 요구하는 대로 조건문을 짜면 됩니다. 난이도는 B4를 기여했습니다.

1월 27일

1208. 부분수열의 합 2 (G1)

2026년의 141번째 문제입니다. 먼저 주어진 배열을 반으로 나누어 줍니다. 각 부분 배열에 브루트 포스를 적용하는 데 $O(2^\frac{N}{2}N)$이 걸리고, 해시맵으로 결과를 구하는 데 다시 $O(2^\frac{N}{2}N)$이 걸립니다. 따라서 총 시간 복잡도 $O(2^\frac{N}{2}N)$에 전체 문제를 해결할 수 있습니다. 이때 최대 하나의 부분 배열에서 아무것도 뽑지 않을 수 있음에 유의합시다. 또한 트리맵을 쓰면 로그 시간이 추가로 붙기 때문에 TLE가 날 수도 있습니다. 난이도는 G2를 기여했습니다.

13146. 같은 수로 만들기 2 (P5)

2026년의 142번째 문제입니다. 배열의 최댓값과 직전 값만을 관리하며 해결할 수 있습니다. 직전 값이 현재 값보다 작다면, Add 연산을 그 차이만큼 시행해 주어 현재 값만 있는 것과 동치로 만들어 줍니다. 또한 직전 값과 현재 값의 대소에 무관하게 최댓값과 직전 값 갱신을 진행합니다. 이 과정을 반복하면 $(시행한~\textrm{Add}의~수)+(최댓값)-(마지막~값)$이 답이 됩니다. 난이도는 P5를 기여했습니다.

2374. 같은 수로 만들기 (G4)

2026년의 143번째 문제입니다. #13146과 같은 문제인데, 제한이 더 작습니다. 따라서 전의 코드를 그대로 제출했습니다. 난이도는 기존 기여를 참고하여 G4를 기여했습니다.

34414. Tall Enough (B4)

2026년의 144번째 문제입니다. 입력받은 정수 중 $48$보다 작은 수가 있다면 False, 없다면 True를 출력하는 문제입니다. 난이도는 B5를 기여했습니다.

34584. Take It or Double It (B4)

2026년의 145번째 문제입니다. $2x>d$이면 take it을, 그렇지 않으면 double it을 출력합니다. 난이도는 B5를 기여했습니다.

1월 28일

30626. 심심한 마루 (S1)

2026년의 146번째 문제입니다. 중심각과 원주각의 관계에 의해 두 점 $L$과 $R$의 각도는 각각 $180+a^\circ+b^\circ$, $180+a^\circ-b^\circ$입니다. 이제 차분 배열 트릭을 사용해 $O(N)$에 문제를 해결해 줍시다. 난이도는 G5를 기여했습니다.

35110. Swap, then record (P4)

2026년의 147번째 문제입니다. 배열 $A$를 정렬하여 $S$를 만들었다고 할 때, $S$에서 인접한 두 원소의 쌍만을 이용하여 배열을 정렬할 수 있을 것처럼 보이고, 실제로도 그렇습니다. 따라서 답의 상한은 $\max(A)-\min(A)$인데, 여기에서 답을 더 줄일 수 있습니다. $k$번 위치와 $k+1$번 위치 사이를 건너지 않고 정렬이 가능하다면 $S_{k+1}-S_k$를 답에서 빼 줄 수 있습니다. 난이도는 P3를 기여했습니다.

1535. 안녕 (S2)

2026년의 148번째 문제입니다. 배낭 문제처럼 보이지만, $N$이 $20$보다 작으므로 브루트 포스가 가능합니다. 난이도는 S1을 기여했습니다.

30658. Os últimos serão os primeiros (B4)

2026년의 149번째 문제입니다. 입력받은 배열마다 뒤집어 출력해 주면 됩니다. 난이도는 B4를 기여했습니다.

25932. Find the Twins (B4)

2026년의 150번째 문제입니다. 문제에서 요구하는 대로 구현해 주면 됩니다. 난이도는 B4를 기여했습니다.

1월 29일

2629. 양팔저울 (G3)

2026년의 151번째 문제입니다. $DP[i][j]$를 $i$번째 추까지만 사용하여 $(왼쪽~무게)-(오른쪽~무게)=j-15000$을 만족시킬 수 있는지 여부로 정의합니다. 초깃값은 $DP[0][15000]=\textrm{True}$, $j\ne15000$일 때 $DP[0][j]=\textrm{False}$입니다. 이제 점화식을 세워봅시다. $DP[i][j]$는 다음의 값들을 or 연산한 값입니다.

• $DP[i-1][j]$
• $DP[i-1][j-w_i]$ ($w_i$는 $i$번째 추의 무게)
• $DP[i-1][j+w_i]$

DP 점화식을 모두 채우면 특정 구슬의 무게를 계산할 수 있는지 여부는 쉽게 판단할 수 있습니다. 난이도는 G3를 기여했습니다.

34529. Acquiring SW-IT Corn (B4)

2026년의 152번째 문제입니다. 그냥 계산해 주면 되는 문제입니다. 난이도는 B5를 기여했습니다.

34543. 와우산 스탬프 투어 (B4)

2026년의 153번째 문제입니다. 문제에서 요구하는 대로 점수를 계산해 줍시다. 난이도는 B4를 기여했습니다.

34306. M-Climb Road (B4)

2026년의 154번째 문제입니다. $\lfloor\frac{5280W}{N}\rfloor$을 출력해 주면 됩니다. 난이도는 B4를 기여했습니다.

34183. SUAPC 의자 준비하기 (B4)

2026년의 155번째 문제입니다. $3N\le{}M$이라면 $0$을, 그렇지 않다면 $A(3N-M)+B$를 출력해 줍시다. 난이도는 B5를 기여했습니다.

1월 30일

17623. 괄호 (G2)

2026년의 156번째 문제입니다. 괄호값이 $x$인 문자열 중 dmap이 가장 작은 것을 $S_x$라 합시다. $4$ 이상의 자연수 $x$에 대해, $S_x$로 가능한 후보는 다음과 같습니다.

• ( + $S_\frac{x}{2}$ + )
• { + $S_\frac{x}{3}$ + }
• [ + $S_\frac{x}{5}$ + ]
• $S_i$ + $S_{x-i}$ ($1\le{}i<x$)

이것들 중 문자열의 길이가 가장 작은 것, 길이가 같다면 (){}[] 순으로 문자 순서를 정의할 때 사전순으로 앞서는 것(실제 사전순은 이것과 다름)이 $S_x$가 됩니다. 이 방식으로 $S_{1000}$까지를 미리 구하고, 입력에 따라 출력하면 되겠습니다. 난이도는 G2를 기여했습니다.

34326. 숭고한에 어서오세요 (B4)

2026년의 157번째 문제입니다. 공차를 잘 찾은 뒤, 마지막 원소에 더해 주면 됩니다. 난이도는 B4를 기여했습니다.

34308. Abby's Absolutes (B4)

2026년의 158번째 문제입니다. 배열의 $i$번째 원소를 $A_i$라 할 때, $N-A_i<A_i-1$이면 $N$을, 그렇지 않으면 $1$을 출력합니다.

34552. 디딤돌 장학금 (B4)

2026년의 159번째 문제입니다. 학점 및 평점 조건을 만족할 경우 분위에 해당하는 금액을 더해주면 됩니다.

34210. A + B Queries (B4)

2026년의 160번째 문제입니다. 두 vector 전역 변수를 만들고, initialize 함수에서는 매개변수를 전역 변수에 저장, ranswer_question 함수에서는 요구하는 합을 구해 주면 됩니다.

1월 31일

2504. 괄호의 값 (G5)

2026년의 161번째 문제입니다. 알고리즘 태그에는 스택이라고 되어 있지만, 저는 DP로 해결했습니다. $DP[i][j]$를 주어진 문자열 $S$의 $i$번째부터 $j$번째까지의 부분 문자열이 갖는 값으로 정의합니다. $4$글자 이상의 부분 문자열에 대하여 $S$의 값은 다음 중 최댓값입니다. (최대 하나를 제외한 나머지 모두 $0$)

• $S[i]$가 (, $S[j]$가 )일 경우, $2\times{}DP[i+1][j-1]$
• $S[i]$가 [, $S[j]$가 ]일 경우, $3\times{}DP[i+1][j-1]$
• $DP[i][k]+DP[k+1][j]$ ($i<k$, $k+1<j$)

이제 탑다운 DP로 값을 구할 수 있습니다.

10448. 유레카 이론 (B1)

2026년의 162번째 문제입니다. $DP[i][j]$를 $j$개의 삼각수로 $i$를 표현할 수 있는지 여부로 정의합니다. 초깃값은 $DP[0][0]=\textrm{True}$, $DP[0][j]=\textrm{False}~(j>0)$입니다. 이제 점화식을 세워 봅시다. $i$ 이하의 삼각수가 $k$개라고 할 때, $DP[i][j]=DP[i-T_1][j-1]~\textrm{or}~DP[i-T_2][j-1]~\textrm{or}~\cdots~\textrm{or}~DP[i-T_k][j-1]$입니다. 이렇게 DP 테이블을 채우면, $DP[n][3]$이 문제의 답이 됩니다.

2961. 도영이가 만든 맛있는 음식 (S2)

2026년의 163번째 문제입니다. 브루트 포스를 해 주는 문제입니다. 아무것도 뽑지 않을 수는 없음에 주의합시다.

10972. 다음 순열 (S3)

2026년의 164번째 문제입니다. C++의 next_permutation 함수로 간단하게 해결할 수 있는 문제입니다.

17608. 막대기 (B2)

2026년의 165번째 문제입니다. 스택을 사용합니다. 왼쪽에 있는 막대기부터 스택에 넣어주는데, 넣기 전 자신보다 짧거나 같은 막대기를 모두 제거합니다. 이것을 반복하면 스택의 남은 막대기의 개수가 답이 됩니다.