2026년 2월 BOJ 정리

2026년 2월에 푼 백준 문제 목록입니다. 총 95문제를 풀었습니다.

2월 1일

2621. 카드게임 (S3)

2026년의 166번째 문제입니다. 시간 복잡도 등을 고려할 필요는 전혀 없고, 열심히 조건 분기를 해주면 됩니다. 저는 각 색깔별 빈도, 숫자별 빈도, 등장하는 최대 숫자를 기준으로 삼았습니다.

28017. 게임을 클리어하자 (G5)

2026년의 167번째 문제입니다. $DP[i][j]$를 $i$회차부터 시작하고 그 회차에 $j$번째 무기를 사용할 때, 얻을 수 있는 최적의 시간으로 정의합니다. 그러면 간단한 탑다운 DP를 통해 문제를 해결할 수 있습니다.

24508. 나도리팡 (G5)

2026년의 168번째 문제입니다. 먼저 나도리의 합이 $K$의 배수가 아닌 경우, 나도리가 없는 경우 등을 예외 처리해 줍니다. 다음으로 배열을 정렬한 뒤, 양 끝에서 시작하여 투 포인터를 돌립니다. 각각 $l$번째와 $r$번째 원소를 가리킨다고 할 때, $l$번째 원소에서 $r$번째 원소로 나도리를 옮깁니다. 모두 옮겼을 때의 총 나도리 수가 $K$ 이상이라면 $K$가 될 때까지만 옮기고, 그렇지 않으면 모두 옮깁니다. 이제 두 경우에 대하여 각각 $r$을 $1$ 감소, $l$을 $1$ 증가시킵니다. 이렇게 나도리를 모두 터트려 주었다면, 옮긴 횟수의 총합을 $T$와 비교해 답을 내면 됩니다.

14919. 분포표 만들기 (S3)

2026년의 169번째 문제입니다. 부동소수점 오차를 없애기 위해, 주어지는 소수를 문자열로 입력받고 $m\times10^6$을 곱한 정수로 바꾸어 줍니다. 이를 $10^6$으로 나눈 몫에 따라 소속 구간이 결정됩니다.

16163. #15164번_제보 (P5)

2026년의 170번째 문제입니다. 매내처 기본 문제입니다. 주어진 문자열의 길이를 $N$, 문자열의 처음과 끝, 각 문자 사이에 더미 문자를 넣은 것을 $T$, $T$의 $i$번째 문자를 중심으로 하는 회문의 최대 반지름을 $p_i$라 합시다. $p_1$부터 $p_{2N+1}$까지의 전체 배열은 매내처를 사용하여 $O(N)$에 구할 수 있습니다. 이제 각 $p_i$에 대해 $\lfloor\frac{p_i+1}{2}\rfloor$의 합을 출력하면 됩니다.

1월 2일

13275. 가장 긴 팰린드롬 부분 문자열 (P5)

2026년의 171번째 문제입니다. 매내처를 사용하여 각 위치를 중심으로 하는 가장 긴 팰린드롬의 길이를 구하고, 이중 최댓값을 출력하면 됩니다.

14444. 가장 긴 팰린드롬 부분 문자열 (P5)

2026년의 172번째 문제입니다. #13275와 완전히 같은 문제입니다. 따라서 solved.ac에서 레이팅을 주지 않습니다.

1월 3일

5624. 좋은 수 (G3)

2026년의 173번째 문제입니다. 배열의 각 원소 $x$에 대해서, 이전 원소들을 갖고 있는 집합 $A$와 이전에 있는 두 원소의 합을 모두 갖고 있는 집합 $B$가 있다고 합시다. $A$와 $B$의 원소 개수는 각 $O(N)$, $O(N^2)$일 것입니다. 이제 $A$의 각 원소 $k$에 대해 $x-k$가 $B$에 존재하는지 판별하고, 그런 경우가 하나라도 있다면 그 수를 좋은 수로 판단합니다. 이제 배열 $A$와 $B$를 현재 원소까지 포함하도록 갱신하고, 이를 반복하면 $O(N^2)$에 문제를 해결할 수 있습니다.

12947. 트리 만들기 (G4)

2026년의 174번째 문데입니다. 어떤 깊이 $d$에 대해 깊이가 $d$인 정점이 $1$개뿐이라면, 그 깊이에 있는 정점을 서브루트라고 합시다. (원래 루트 포함) 서브루트를 깊이 순으로 정렬한다면 $i$번째 서브루트에서 출발하여 $i+1$번째 서브루트를 지나지 않고 도달할 수 있는 최대 깊이는 $i+1$번째 서브루트에서 $1$을 뺀 것과 같습니다. 얻을 수 있는 트리의 지름 최댓값은 깊이 $N$의 정점에서 어떤 서브루트로 올라가고, 그곳에서 다른 방향으로 끝까지 내려갈 때의 이동 거리 최댓값과 같습니다.

5874. 소를 찾아라 (S4)

2026년의 175번째 문제입니다. ((의 등장 횟수를 기록하는 변수를 만들어 줍시다. 초깃값은 $0$입니다. 문자열을 왼쪽부터 순회하며 ((이 나오면 변수에 $1$을 더하고, ))이 나오면 결과에 변수 값을 더해 줍니다.

11046. 팰린드롬?? (P5)

2026년의 176번째 문제입니다. 매내처를 사용하는 문제입니다. 매내처를 돌려 각 위치에서의 회문 반지름을 찾은 뒤, 주어진 구간의 중심에서 회문을 이루는 최대 구간이 주어진 구간보다 작은지 확인하면 됩니다.

2월 4일

18171. ABB (P4)

2026년의 177번째 문제입니다. 이번에도 매내처입니다. 문자열의 중간 지점부터 오른쪽으로 나아가면서 회문 반지름이 문자열의 오른쪽 끝에 닿는 가장 왼쪽 지점을 찾습니다. 이제 그곳을 중심으로 전체 문자열이 회문이 되도록 추가해야 하는 문자의 수를 출력하면 됩니다.

2월 5일

16481. 원 전문가 진우 (P4)

2026년의 178번째 문제입니다. 별도의 알고리즘은 없고, 기하학 날먹 문제입니다. 루리에 정리에 의해 답은 $\frac{1}{\frac{1}{r_1}+\frac{1}{r_2}+\frac{1}{r_3}}$입니다.

2월 6일

13711. LCS 4 (P5)

2026년의 179번째 문제입니다. 각 배열 내에서 중복이 없으므로, 배열 $C$를 만들고 $B_i=A_{C_i}$를 만족하도록 $C$를 유일하게 결정할 수 있습니다. 이제 $C$의 LIS 길이가 답이 됩니다.

2월 7일

15678. 연세워터파크 (P5)

2026년의 180번째 문제입니다. 먼저 밟는 징검다리의 번호는 항상 증가하는 것이 최적임을 관찰합니다. 한 방향으로 가다가 뒤돌아가는 대신 미리 해당 징검다리를 밟고 오면 되기 때문입니다. 이제 $i$번 징검다리를 마지막 징검다리로 하도록 경로를 설정할 때 얻을 수 있는 최대 점수를 $DP[i]$로 정의합시다. 그러면 $DP[i]$는 다음 중 최댓값과 같습니다.

• $K_i$
• $DP[i-1]+K_i$
• $DP[i-2]+K_i$
• ...
• $DP[\max(i-D,1)]+K_i$

$K_i$는 나중에 더한다고 하면 $DP[i-1]$부터 $DP[\max(i-D,1)]$까지의 값들과 $0$만이 남는데, 이들 중 최댓값은 덱을 이용한 구간 최댓값 트릭으로 관리할 수 있습니다. 이렇게 DP 테이블을 모두 채운 뒤, 전체 테이블에서 최댓값을 출력해 줍시다.

2월 8일

31264. 사격 (G5)

2026년의 181번째 문제입니다. 먼저 배열 $s$를 정렬한 뒤, 매개 변수 탐색을 돌립니다. 초기 사격 실력 $C$에 대하여 이분 탐색으로 맞힐 수 있는 가장 높은 점수의 표적을 찾아 맞히는 것을 $M$번 반복합니다. 최종적으로 얻은 점수를 $A$와 비교하면 한 번의 탐색을 $O(M\log{N})$에 해결할 수 있습니다. 이것을 $O(\log{A})$번 하게 되고, 맨 처음 정렬에 $O(N\log{N})$의 시간이 걸리므로 전체 시간 복잡도는 $O((N+M\log{A})\log{N})$입니다.

23035. 가톨릭대는 고양이를 사랑해 (P4)

2026년의 182번째 문제입니다. 먼저 제한을 살펴봅시다. $N$과 $M$의 제한이 매우 큰 반면, $T$의 제한은 상대적으로 작습니다. 따라서 $O(N)$이나 $O(M)$ 이상의 시간 복잡도는 불가능함을 알 수 있습니다. 문제 상황을 보면 쿠기는 오른쪽이나 아래로만 이동할 수 있습니다. 그러나 DP를 사용하기에는 $N$과 $M$이 매우 크므로, LIS를 사용해 줍시다. 고양이들을 $(r,c)$ 기준으로 정렬한 뒤, $(c,r)$ 기준으로 LIS 길이를 구해 출력합니다. 가톨릭대 밖에 있는 고양이는 당연히 고려하지 않습니다.

2월 9일

31503. DP (Large) (P5)

2026년의 183번째 문제입니다. 길이 $N$의 어떤 배열이 있을 때, $1$ 이상 $N$ 이하의 각 $i$에 대하여 $i$번째 원소로 끝나는 LIS의 길이는 총 $O(N\log{N})$에 구할 수 있습니다. 이를 이용하여 각 원소로 끝나는 LIS의 길이와, 배열을 뒤집었을 때 각 원소로 끝나는 LDS의 길이(각 원소로 시작하는 LIS의 길이와 같음)를 구해 줍니다. 두 값을 각각 $e_i$, $s_i$라 하면 $e_i+s_i-1$이 쿼리의 답이 됩니다.

31501. DP (Small) (G3)

2026년의 184번째 문제입니다. #31503의 너프 버전입니다. 같은 코드를 그대로 제출해 줍시다.

2월 10일

16474. 이상한 전깃줄 (P5)

2026년의 185번째 문제입니다. 도로 왼편과 오른편에서 $i$번째 전봇대의 번호를 각각 $A_i$, $B_i$라 합시다. 전깃줄 $(a,b)$가 입력될 때, $A_x=a$와 $B_y=b$를 모두 만족하는 $x$, $y$에 대하여 $(x,y)$를 저장해 줍니다. 이제 $K$개의 쌍을 $x$가 커지는 순, 같다면 $y$가 작아지는 순으로 정렬합니다. 마지막으로 각 쌍에서 뒤 원소만 모은 배열의 LIS를 구하면 $K-(\textrm{LIS~길이})$가 답이 됩니다.

2월 11일

2995. 생일 (P4)

2026년의 186번째 문제입니다. #16474와 유사하게 $A$가 커지는 순, $A$가 같다면 $B$가 작아지는 순으로 구간을 정렬합니다. 이제 $B$의 값을 기준으로 가장 긴 단조 감소 배열을 하나 찾아 출력하면 됩니다.

2월 12일

15900. 나무 탈출 (S1)

2026년의 187번째 문제입니다. 각 리프 노드에 대하여 루트 노드에 이르는 거리의 합을 구합니다. 이 합이 홀수이면 답은 Yes, 짝수이면 다은 No입니다.

1086. 박성원 (P5)

2026년의 188번째 문제입니다. 먼저 전처리를 합니다. 수를 그대로 저장하기에는 매우 크므로, 문자열로 입력을 받으면서 $K$로 나눈 나머지만을 저장합니다. 또한 이 값을 $A$라 할 때, $10A,100A,\cdots,10^{5000}A$를 $K$로 나눈 나머지도 저장해 줍니다.

다음으로 정답이 되는 순열의 개수를 구합니다. 비트마스킹을 활용해 $N$자리 이진수로 각 정수의 선택 여부를 확인할 때, 각 이진수 $i$에 대응되는 선택 여부를 상태 $i$라 합시다. 이때 $DP[i][j]$를 상태 $i$가 되도록 순열을 만들 때, 합친수를 $K$로 나눈 나머지가 $j$가 되도록 하는 경우의 수로 정의합니다. 초깃값은 $DP[0][0]=1$, $DP[0][j]=0$ ($0<j<K$)입니다. 이제 점화식을 세워 봅시다. 점화식은 직접 설명하기 힘들기 때문에, 코드를 첨부하도록 하겠습니다.

마지막으로 $\frac{DP[2^N-1][0]}{N!}$을 기약분수로 만들어 출력하면 답이 됩니다.

2월 13일

26076. 곰곰이의 식단 관리 2 (P5)

2026년의 189번째 문제입니다. $N=1$이거나 $M=1$일 때는 예외 처리를 합니다. 장애물이 있다면 답은 $0$, 없다면 $1$입니다. 나머지 경우에는 0-1 BFS를 사용하여 문제를 해결할 수 있습니다. 오른쪽과 위의 두 변을 A, 왼쪽과 아래의 두 변을 B라 할 때, 장애물은 가중치 $0$, 빈칸은 가중치 $1$로 하여 A와 B를 잇는 최단 경로를 구하면 됩니다. 이때 대각선도 인접한 칸으로 보아야 함에 유의합니다.

2460. 지능형 기차 2 (B3)

2026년의 190번째 문제입니다. 각 역마다 사람 수를 직접 관리해 주면 됩니다. 내리는 것과 타는 것 사이에서 인원 수가 최대일 수는 없으므로, 탄 후만 확인해도 됩니다.

2010. 플러그 (B3)

2026년의 191번째 문제입니다. 다음 멀티탭을 연결하기 위해 콘센트 $N-1$개가 소모됩니다. 따라서 개수 총합에서 이것을 빼 주면 됩니다.

10996. 별 찍기 - 21 (B2)

2026년의 192번째 문제입니다. 예제를 보자마자 알 수 있는 그 규칙대로 짜면 됩니다. 참 쉽죠?

2506. 점수계산 (B3)

2026년의 193번째 문제입니다. 총점 변수와 연속 정답 횟수 변수를 각각 관리하면 됩니다.

4796. 캠핑 (B1)

2026년의 194번째 문제입니다. $L$일 동안 캠핑장을 이용하고, $P-L$일 동안 이용하지 않는 것을 반복하는 것이 최적입니다.

2875. 대회 or 인턴 (B3)

2026년의 195번째 문제입니다. 먼저 최대한 대회 팀을 짜줍니다. 팀을 짜지 못한 학생은 모두 인턴으로 보냅니다. 인턴이 $K$명 미만이라면 최소한의 대회 팀을 인턴으로 옮깁니다.

2월 14일

5573. 산책 (P3)

2026년의 196번째 문제입니다. $(i,j)$를 $K$번 방문한다 했을 때, $(i+1,j)$와 $(i,j+1)$을 절반씩 방문하게 됩니다. 이를 이용해 $DP[i][j]$를 $N-1$번의 산책 후 $(i,j)$의 방문 횟수로 정의하여 점화식을 세울 수 있고, DP 테이블이 모두 채워지면 시뮬레이션을 통해 $N$번째 산책의 도착지를 구할 수 있습니다.

25418. 정수 a를 k로 만들기 (S3)

2026년의 197번째 문제입니다. DP와 BFS를 모두 사용할 수 있는데, 여기에서는 DP를 사용해 보겠습니다. $DP[i]$를 $A$에서 시작하여 $i$를 만드는 데 필요한 최소한의 연산 횟수로 정의합니다. 초깃값은 $i<A$일 때 $DP[i]=∞$, $DP[A]=0$입니다. 이제 점화식을 세워 봅시다. $i>A$일 때 $DP[i]$는 다음과 같습니다.

• $i$가 홀수인 경우, $DP[i-1]+1$
• $i$가 짝수인 경우, $\min(DP[i-1],DP[\frac{i}{2}])+1$

이제 $DP[K]$가 문제의 정답이 됩니다.

13699. 점화식 (S4)

2026년의 198번째 문제입니다. $t(35)<2^{63}-1$임을 믿고 주어진 점화식대로 탑다운 DP를 짜서 제출했고, Proof by AC했습니다.

14651. 걷다보니 신천역 삼 (Large) (S1)

2026년의 199번째 문제입니다. $N=1$이면 답은 $0$임이 자명합니다. $N\ge2$인 경우를 잘 생각해 보면, $3$으로 나눈 나머지가 $0$, $1$, $2$인 수의 개수가 모두 같음을 알 수 있습니다. 전체 경우의 수가 $2\times3^{N-1}$이므로 $2\times3^{N-2}$를 $10^9+9$로 나눈 나머지가 답입니다.

2810. 컵홀더 (B1)

2026년의 200번째 문제입니다. 커플석이 없다면 사용할 수 있는 컵홀더의 개수는 좌석의 수와 같습니다. 커플석이 하나라도 있다면 사용할 수 있는 컵홀더의 개수는 전체 컵홀더의 개수와 같습니다. 이 값은 $\textrm{S의 개수}-\frac{\textrm{L의 개수}}{2}+1$과 같습니다.

30700. KOREA 문자열 만들기 (B2)

2026년의 201번째 문제입니다. 문자열을 앞에서부터 읽으면서 K, O, R, E, A를 이 순서대로 그리디하게 찾으면 됩니다.

19564. 반복 (B1)

2026년의 202번째 문제입니다. $i$번째 문자가 $i-1$번째 문자보다 사전 순으로 뒤에 있다면, $i$번째 문자를 입력하기 위해 자판을 다시 누를 필요가 없습니다. 그렇지 않다면 새 반복을 해야 합니다.

32978. 아 맞다 마늘 (B3)

2026년의 203번째 문제입니다. 각 재료를 집합에 담고, 사용한 것을 하나씩 빼주면 되는 단순한 문제입니다.

2월 15일

1533. 길의 개수 (P3)

2026년의 204번째 문제입니다. 각 정점 $v$를 5개로 나누고, 이를 $v_1,v_2,\cdots,v_5$라 합시다. $v_5\to{}v_4,v_4\to{}v_3,\cdots,v_2\to{}v_1$ 간선을 각각 만들어 주고, 정점 $i$에서 $j$로 가는 경로의 길이가 $k$일 때 $i_1\to{}j_k$ 간선을 만들어 줍니다. 이 인접행렬을 $T$제곱한 뒤 $S_1\to{}E_1$의 값을 구하면 됩니다.

5107. 마니또 (S1)

2026년의 205번째 문제입니다. 맵으로 마니또 관계를 정리하고, 간선을 쭉 따라가 주면 됩니다. indegree와 outdegree가 각각 $1$이므로, ρ 형태가 존재하지 않음은 증명 가능합니다.

34671. 무토의 일본 여행 (S3)

2026년의 206번째 문제입니다. 이동에 정확히 한 가지 간선만을 이용할 수 있으므로, 간선 자체를 맵에 저장하고 존재하는지 검사하는 방식이 가능합니다.

27160. 할리갈리 (B2)

2026년의 207번째 문제입니다. 맵에 키 4개를 미리 등록해 놓은 다음, 입력에 따라 값을 갱신해 주면 됩니다.

6322. 직각 삼각형의 두 변 (B3)

2026년의 208번째 문제입니다. 피타고라스 정리를 그대로 사용하되, 직각을 낀 변의 길이가 빗변보다 길 때만 Impossible.을 출력하면 됩니다.

16485. 작도하자! - ② (B2)

2026년의 209번째 문제입니다. 내각의 이등분선의 성질에 의해, 답은 $\frac{a}{b}$입니다.

32573. Cowpproximation (P1)

2026년의 210번째 문제입니다. 최적의 약속 장소에 대하여, 답은 해당 점에 도달하기 위해 가장 많이 이동해야 하는 소의 이동 거리와 같습니다. 따라서 경사 하강법을 활용하여 최소 외접원을 구하는 기법을 응용하여 해결해 줍시다.

13552. 구와 쿼리 (B1)

2026년의 211번째 문제입니다. 시간 제한이 20초로 매우 여유롭기 때문에 브루트 포스가 가능한 문제입니다.

2월 16일

13306. 트리 (P4)

2026년의 212번째 문제입니다. 모든 쿼리를 처리한 후에는 간선이 하나도 없게 됩니다. 따라서 간선이 하나도 없는 상태에서 쿼리를 나중에 들어온 것부터 처리해 줍니다. 간선 삭제 쿼리는 생성 쿼리로 해석하고, Union-Find를 사용하여 풀면 됩니다.

34922. 사각지대 (B3)

2026년의 213번째 문제입니다. 답은 매우 당연하게 $wh-\frac{\pi{}r^2}{4}$입니다.

31945. 정육면체의 네 꼭짓점 (B2)

2026년의 214번째 문제입니다. x, y, z좌표 중 하나가 모두 같아야 한 면 위에 있는 것이므로, 점 번호에 대한 비트 연산으로 잘 해결할 수 있습니다.

16972. 814 - 1 (B1)

2026년의 215번째 문제입니다. 문제에 AC 기준이 명시되어 있지 않으므로, 점수에 관계없이 (즉, 출력값이 최대가 아니더라도) 다른 조건을 모두 만족하면 AC가 됩니다! $28\times29=812$이므로, 격자 형태로 $812$개의 점을 배열한 뒤 남은 $2$개의 점을 충분히 멀리 떨어진 곳에 격자 간격보다 가깡 놓으면 됩니다.

11880. 개미 (B2)

2026년의 216번째 문제입니다. $(a+b)^2+c^2$, $(a+c)^2+b^2$, $(b+c)^2+a^2$ 중 최솟값을 출력하면 됩니다.

32217. 광선 다각형 만들기 (B1)

2026년의 217번째 문제입니다. $n+1$각형의 내각의 크기의 합은 $180°(n-1)$임이 잘 알려져 있습니다. 따라서 모든 $\theta_i$의 합에 $2$를 곱한 값을 여기에서 빼 주면 됩니다.

22238. 가희와 btd5 (G4)

2026년의 218번째 문제입니다. 문제의 조건에 따라, 모든 풍선은 타워를 시점으로 하는 하나의 반직선 위에 존재합니다. 즉, 한 번의 공격은 모든 풍선에 영향을 주거나, 영향을 아예 주지 않습니다. 영향을 주는 공격인지 먼저 계산하고, 이분 탐색을 통해 남아 있는 풍선의 개수를 구하면 됩니다.

34563. 궁핍한 모그 (B2)

2026년의 219번째 문제입니다. 가로선 하나와 세로선 하나를 잡아 커넥터를 줄줄이 붙이는 게 최적이고, 그때의 개수는 $N+M-1$개입니다.

16478. 원의 분할 (B1)

2026년의 220번째 문제입니다. 답은 $\frac{p_{ab}p_{cd}}{p_{bc}}$입니다.

11896. 다각형 (S5)

2026년의 221번째 문제입니다. 변이 짝수 개이면 조건을 만족하고, 홀수 개이면 만족하지 않습니다.

16483. 접시 속의 원 (B2)

2026년의 222번째 문제입니다. 답은 $(\frac{T}{2})^2$입니다.

33835. 도로 공사 (B1)

2026년의 223번째 문제입니다. 삼각 부등식에 의해, 모든 도로를 철거한 뒤 $1$번과 $N$번 마을을 직접 잇는 도로를 건설할 수 있으며, 이것이 최적입니다.

15687. 직사각형 (S5)

2026년의 224번째 문제입니다. 문제에서 요구하는 대로 멤버 함수를 짜 주면 되는 단순한 문제입니다.

33884. 클리크 조절 (B1)

2026년의 225번째 문제입니다. 각 훈련에서 점을 정렬해 주고, 맨 처음 점만 비교해 주면 됩니다.

2월 17일

16978. 수열과 쿼리 22 (P4)

2026년의 226번째 문제입니다. 오프라인 쿼리를 활용하는 문제입니다. 1번 쿼리를 저장하는 배열 $X$, 2번 쿼리를 저장하는 2차원 배열 $Y$, 쿼리의 결과를 저장하는 배열 $Z$를 만듭니다. 1번 쿼리가 들어오면 $X$에 저장하고, 2번 쿼리가 들어오면 현재까지 들어온 2번 쿼리의 개수 $q$에 대하여 $(q,i,j)$를 $Y_k$에 저장합니다.

$X$와 $Y$를 채우고 나면, $Y_k$에 있는 2번 쿼리를 모두 답하고 $k$번째 1번 쿼리를 처리하는 작업을 반복합니다. 이때 2번 쿼리의 결과는 바로 출력하는 대신 $Z[q]$에 저장하고, 자료구조는 일반적인 세그먼트 트리를 사용합니다. 마지막으로 $Z$에 저장된 결과값을 차례대로 출력하면 AC를 받을 수 있습니다.

2월 18일

10246. 부동산 경매 (S1)

2026년의 227번째 문제입니다. $n$원짜리 집부터 $n+k-1$원짜리 집까지 구매하는 데 드는 총액은 $kn+\frac{k(k-1)}{2}$원입니다. 이 값이 $10^6$ 이하가 되는 모든 $(k,n)$에 대해 브루트 포스를 돌리면 됩니다. 조화수열의 성질에 의해 시간 복잡도는 $N=10^6$에 대해 $O(N\log{N})$ 이하임이 보장됩니다.

1693. 트리 색칠하기 (P2)

2026년의 228번째 문제입니다. 첫 번째로 할 수 있는 관찰은 사용해야 하는 최대 색 번호 $c$가 $N$에 비해 현저히 작다는 것입니다. $c$가 $O(\log{N})$에 bound되는 것은 쉽게 증명할 수 있습니다. 따라서 $DP[i][j]$를 $i$번 정점을 루트로 하는 서브트리에 대하여 $i$번 정점을 $j$번 색으로 칠할 때의 최소 비용으로 정의하고, $1$번 정점을 전체 트리의 루트로 하여 트리 DP를 돌렸습니다. $c\le20$으로 가정하고 믿음의 제출을 했고, Proof by AC했습니다.

14606. 피자 (Small) (S5)

2026년의 229번째 문제입니다. $DP[i]$를 $N=i$일 때의 답으로 정의합시다. 초깃값은 $DP[1]=0$입니다. 그러면 $i>1$일 때 $DP[i]=\max_{j=1}^{i-1}(j(i-j)+DP[j]+DP[i-j])$입니다. 이를 그대로 구현하면 AC를 받을 수 있습니다.

14607. 피자 (Large) (S3)

2026년의 230번째 문제입니다. 예제를 잘 보니, 답이 $\frac{N(N-1)}{2}$와 같다는 생각이 듭니다. 그리고 Proof by AC했습니다.

24417. 알고리즘 수업 - 피보나치 수 2 (S4)

2026년의 231번째 문제입니다. 입력으로 들어오는 $N$에 대하여, $N$번째 피보나치 수와 $N-2$를 각각 출력하면 됩니다.

17212. 달나라 토끼를 위한 구매대금 지불 도우미 (S3)

2026년의 232번째 문제입니다. $DP[i]$를 $i$원을 지불하기 위해 필요한 최소한의 동전 개수로 정의합시다. 그러면 $DP[0]=0$이고, $DP[i]$는 다음 중 최솟값과 같습니다.

• $DP[i-1]+1$
• $i\ge2$일 때, $DP[i-2]+1$
• $i\ge5$일 때, $DP[i-5]+1$
• $i\ge7$일 때, $DP[i-7]+1$

이것을 그대로 구현한 뒤 $DP[N]$을 출력하면 정답입니다.

11034. 캥거루 세마리2 (B3)

2026년의 233번째 문제입니다. 캥거루 사이 공간이 두 곳 생기게 되는데, 이중 더 넓은 곳에서 한 칸씩 좁혀 가는 것이 최적입니다. 따라서 정답은 $\max(B-A,C-B)-1$입니다.

28014. 첨탑 밀어서 부수기 (B3)

2026년의 234번째 문제입니다. 앞에서부터 연속되는 감소 수열의 개수를 세 주면 됩니다.

30018. 타슈 (B3)

2026년의 235번째 문제입니다. 각 대여소를 자전거가 줄어든 곳과 늘어난 곳으로 나누면, 자전거 대수 변화량의 절댓값은 양쪽이 같습니다. 이 절댓값을 $K$라 할 때, $K$회만에 자전거를 모두 옮길 수 있음과 $K-1$회 이하로 옮길 수 없음이 모두 자명하므로, $K$가 답이 됩니다.

2월 19일

26146. 즉흥 여행 (Easy) (P5)

2026년의 236번째 문제입니다. SCC 기초 문제로, 주어진 그래프의 SCC가 1개라면 Yes, 그렇지 않다면 No를 출력하면 됩니다.

18238. ZOAC 2 (B2)

2026년의 237번째 문제입니다. 문자열의 맨 앞에 A를 추가하고, 각 $i$에 대하여 $i$번째 문자에서 $i+1$번째 문자로 이동하는 시간을 모두 더하면 됩니다.

31880. K512컵 개최! (B2)

2026년의 238번째 문제입니다. $0$이 적힌 곱셈 주문서는 행운을 $0$으로 만들기 때문에 가장 먼저 사용해야 합니다. 다음으로 모든 덧셈 주문서, 모든 곱셈 주문서 순서로 사용하는 것이 최적입니다.

21313. 문어 (B2)

2026년의 239번째 문제입니다. $N$이 짝수라면 1 2 ... 1 2, 홀수라면 1 2 ... 1 2 3이 최적입니다.

14720. 우유 축제 (B2)

2026년의 240번째 문제입니다. 앞에서부터 0, 1, 2가 반복되는 것만 취해주면 되는 단순한 문제입니다.

25176. 청정수열 (Easy) (B1)

2026년의 241번째 문제입니다. 두 개의 $i$ 사이에 있는 수의 합은 적어도 $2i$입니다. 모든 $i$에 대하여 이 조건을 만족시키려면 두 $i$가 항상 인접하면 됩니다. 따라서 답은 $N!$입니다.

33572. 자세히 보아야 예쁘다 (B2)

2026년의 242번째 문제입니다. $i$번 친구는 최대 $A_i-1$시간 볼 수 있으므로, $\sum_{i=1}^NA_i-N\ge{}M$이면 DIMI를, 그렇지 않으면 OUT을 출력하면 됩니다.

28062. 준석이의 사탕 사기 (B2)

2026년의 243번째 문제입니다. 모든 $a_i$의 합이 짝수라면 그대로 출력하고, 홀수라면 최소의 홀수 $a_i$를 뺀 값을 출력합니다.

2월 20일

32437. Fractions are better when continued (B1)

2026년의 244번째 문제입니다. $p_0=1,~p_n=\frac{1}{1+p_{n-1}}$입니다. $F_n$을 $n$번째 피보나치 수라 할 때, $\frac{F_1}{F_2}=1,~\frac{F_{n+1}}{F_{n+2}}=\frac{1}{1+{\frac{F_n}{F_{n+1}}}}$입니다. 따라서 $p_n=\frac{F_{n+1}}{F_{n+2}}$입니다. 즉 주어지는 $N$에 대하여 $F_{N+1}$을 출력하면 정답이 됩니다.

26529. Bunnies (B2)

2026년의 245번째 문제입니다. 문제에서 주어지는 $F(N)$을 출력하면 되는 간단한 문제입니다.

11568. 민균이의 계략 (S2)

2026년의 246번째 문제입니다. #11053과 같은 문제임을 쉽게 알 수 있습니다. LIS를 $O(N^2)$으로 구하면 됩니다.

18859. 부모님께 큰절 하고 (P4)

2026년의 247번째 문제입니다. 문제에서 요구하는 "예술적인 큰절"은 수열의 최솟값을 초항으로 하는 양수 공차의 등차수열이 2개 있는 것과 같습니다. 이때 두 등차수열에 모두 들어갈 수 있는 항을 생각해 봅시다. 한 등차수열의 양 끝 값만이 (최솟값, 최댓값) 가능하다는 것을 알 수 있습니다. 따라서 배열을 정렬해 준 뒤 첫 번째 원소와 두 번째 원소를 포함하는 등차수열을 최대한 제거합니다. 다음으로 그 등차수열의 최솟값은 반드시 포함하고, 최댓값을 포함하는 경우와 하지 않는 경우 각각에 대하여 등차수열 여부를 검사합니다. 둘 중 하나라도 만족한다면 답은 Yes, 그렇지 않다면 답은 No입니다.

12849. 본대 산책 (S1)

2026년의 248번째 문제입니다. 제한이 더 큰 버전인 #12850을 이미 풀었기 때문에 그대로 제출했습니다.

14430. 자원 캐기 (S2)

2026년의 249번째 문제입니다. $A[i][j]$를 $(i,j)$의 광석 수로, $DP[i][j]$를 $(i,j)$에 도착할 때 얻을 수 있는 최대 광석 수로 정의합니다. 초깃값은 $DP[1][1]=A[1][1]$입니다. 이제 점화식을 세워봅시다. $DP[1][j]=DP[1][j-1]+A[1][j]$, $DP[i][1]=DP[i-1][1]+A[i][1]$, $DP[i][j]=\max(DP[i][j-1],DP[i-1][j])+A[i][j]$입니다. 이를 구현하고 $DP[N][M]$을 출력해 주면 됩니다.

2월 21일

11920. 버블 정렬 (P2)

2026년의 250번째 문제입니다. 입력된 배열에서 맨 앞 $K+1$개의 원소를 우선순위 큐에 넣고, 가장 작은 값을 빼내어 출력합니다. 다음으로 $K+2$번째 원소를 넣고 최솟값을 빼고, $K+3$번째 원소를 넣고 최솟값을 빼는 것을 반복하여 $N$번째 원소까지 시행해 줍니다. 더 넣을 원소가 없다면 마지막으로 남은 원소를 작은 순으로 쭉 빼내어 출력해 줍니다. 만약 $K=N$이라면 그냥 정렬해서 출력하면 됩니다.

2월 22일

28080. 인경호의 나무 (P5)

2026년의 251번째 문제입니다. $N$과 $M$이 들어오면 먼저 $0\le{}x\le{}M$, $0\le{}y\le{}x$에 대해 $_x\textrm{C}_ y (\textrm{mod}~10^9+7)$을 전처리합니다. 다음으로 트리를 중위 순회한 결과를 배열에 담아주고, 양 끝에 $0$과 $M+1$을 넣습니다. 이제 배열을 처음부터 보면서 연속된 $-1$의 개수와 그 양 옆의 수를 저장합니다. $a$와 $b$ 사이에 $-1$이 $k$개 들어가 있다면, $k$개의 $-1$ 자리에 수를 채우는 경우의 수는 $_{b-a-1}\textrm{C}_ k$입니다. 이 값들의 전체 곱을 $10^9+7$로 나눈 나머지가 답이 됩니다.

2월 23일

1981. 배열에서 이동 (P5)

2026년의 252번째 문제입니다. 경로의 모든 값이 $s$ 이상 $e$ 이하가 되도록 경로를 찾는 것은 BFS로 $O(N^2)$에 가능합니다. $s=e=0$에서 시작하여 투 포인터를 활용해 줍시다. 경로 찾기에 성공했다면 $s$를, 실패했다면 $e$를 증가시키면서 결과값을 갱신하면, 배열의 적힌 수의 최댓값과 최솟값의 차이를 $M$이라 할 때 $O(N^2M)$에 해결할 수 있습니다. 이 문제에서 $M\le200$이므로 시간 내에 해결 가능합니다.

2월 24일

2873. 롤러코스터 (P3)

2026년의 253번째 문제입니다. $R$과 $C$ 중 하나라도 홀수라면, 홀수 번 지그재그 이동을 할 수 있도록 경로를 설정하여 모든 칸을 지날 수 있습니다. 그러나 $R$과 $C$가 모두 짝수라면, $(\textrm{행 인덱스})+(\textrm{열 인덱스})$가 홀수인 칸 하나를 지나지 못하게 됩니다. 당연히 기쁨 값이 가장 작은 칸을 지나지 않는 것이 합리적입니다. 특정 칸만 통과하기 위해서는 그 칸을 포함하는 두 행을 하나로 묶어, 그 사이에서 수직 지그재그를 하면 됩니다.

14442. 벽 부수고 이동하기 2 (G3)

2026년의 254번째 문제입니다. 각 칸에 대하여 벽을 부순 횟수가 $0$회, $1$회, ..., $K$회일 때 접근 가능한 정점을 만들어 줍니다. 그 후 $(N,M)$에 대한 임의의 정점에 도달하는 최단 거리를 시작점과 도착점을 포함하여 구하면 됩니다. $NMK\le10^7$이기 때문에 $O(NMK)$의 나이브한 BFS가 시간 내에 동작합니다.

2월 25일

15783. 세진 바이러스 (P4)

2026년의 255번째 문제입니다. SCC를 구해준 뒤, Indegree가 $0$인 SCC의 개수를 출력하면 됩니다. 즉, #4196과 풀이가 같습니다.

2월 26일

17074. 정렬 (S1)

2026년의 256번째 문제입니다. $a_i>a_{i+1}$인 경우가 없으면 답은 $N$, $2$개 이상이면 답은 $0$입니다. $1$개일 경우, $a_i$를 제거하는 것과 $a_{i+1}$을 제거하는 것을 각각 따져 $1$개 혹은 $2$개로 답을 정해 주면 됩니다.

20304. 비밀번호 제작 (P5)

2026년의 257번째 문제입니다. 각각의 $p_i$를 출발점으로 하여 BFS를 돌립니다. 정점은 각 정수이고, 비트가 한 자리만 차이나는 수끼리 간선으로 잇습니다. 이제 최단 경로의 최댓값을 출력해 주면 답이 됩니다.

2월 27일

1019. 책 페이지 (P5)

2026년의 258번째 문제입니다. 주어진 수가 $K$자리라 하면, $0$이 $K$번 등장하는 것부터 $N$까지의 숫자 개수를 먼저 세어 줍니다. 이는 각 자리에 특정 수가 몇 번 나올 수 있는지 수식화하여 쉽게 구할 수 있습니다. 이제 불필요한 $0$을 제거합니다. 제거하는 $0$의 개수는 $\sum_{i=1}^{K-1}(10^{K-i-1}\times9i)+K$입니다.

2월 28일

2261. 가장 가까운 두 점 (P2)

2026년의 259번째 문제입니다. 먼저 주어진 점들을 x좌표에 따라 정렬하고, 번호를 매깁니다 $1$번. 점부터 $M$번 점까지만 볼 때의 답은 $d$라 할 때, $M+1$번 점까지 볼 때의 답을 구해 봅시다. 답을 줄일 수 있는 후보군은 $M+1$번 점과의 x좌표 차이와 y좌표 차이가 모두 $d$ 이하일 것입니다. x좌표 차이가 $d$ 이하인 점들을 set으로 관리하면 ($M+1$번 점은 아직 set에 넣지 않음) set에 포함된 점은 끝이 $M$번 점인 구간과 같을 것인데, 이 시작점을 $s$라 하고 갱신 시 $s$를 증가시키면서 점을 제거합니다.

set 갱신이 끝나면, 이 set에 이분 탐색을 적용하여 y좌표 차이가 $d$ 이하인 점들을 찾을 수 있습니다. 이때 set에 포함된 모든 점 사이의 거리는 $d$ 이상이므로 범위에 포함되는 점은 매우 적습니다. 이제 이분 탐색으로 정한 범위에서 전수 조사를 해 $d$를 갱신하고, $M+1$번 점을 set에 넣습니다. 이렇게 set 갱신 - 이분 탐색 - $d$ 갱신을 반복하면 답을 얻을 수 있습니다.

5620. 가장 가까운 두 점의 거리 (P2)

2026년의 260번째 문제입니다. #2261과 완전히 같은 문제로, solved.ac에서 레이팅을 주지 않습니다.