2026년 3월 BOJ 정리

2026년 3월에 푼 백준 문제 목록입니다. ljw1029boj 계정에서 푼 문제만 올립니다.

3월 1일

23324. 어려운 모든 정점 쌍 최단 거리 (G4)

2026년의 261번째 문제입니다. 간선의 가중치가 $1$인 것이 하나뿐이고, 나머지 간선의 가중치는 모두 $0$임에 초점을 맞추어 봅시다. 가중치가 $0$인 간선만 만든 상태에서, 가중치가 $1$인 간선의 두 끝을 각각 $a$, $b$라 합시다. 이때 $a$를 포함한 연결 요소와 $b$를 포함한 연결 요소가 같다면, 가중치 $1$의 간선을 이용할 필요가 없으므로 답은 $0$입니다. 그렇지 않다면, 답은 두 연결 요소의 정점 수를 곱한 것과 같습니다.

3월 2일

15661. 링크와 스타트 (G5)

2026년의 262번째 문제입니다. 가능한 모든 조합의 수는 $2^{N-1}-1$입니다. (한 사람의 소속 팀을 고정할 수 있음) 각 조합에서 능력치의 차이를 구하는 데 $O(N^2)$이 걸리므로, 브루트 포스의 전체 시간 복잡도는 $O(2^NN^2)$입니다. $2^{20}\times20^2≈4\times10^8$이지만, 시간 내에 충분히 통과합니다.

3월 3일

2212. 센서 (G5)

2026년의 263번째 문제입니다. 먼저 $N\le{}K$라면 답은 $0$입니다. 그렇지 않다면, 먼저 전 범위를 수신 가능 영역으로 두고 $K-1$개의 빈칸을 뚫는 것으로 환원할 수 있습니다. 따라서 주어진 센서 위치 배열을 정렬한 뒤 가장 긴 공백 $K-1$개를 찾으면 됩니다.

3월 4일

32404. 일이 커졌어 (G5)

2026년의 264번째 문제입니다. 곱셈의 증가가 덧셈의 증가보다 유의미하게 크기 때문에, 덧셈은 큰 수를 먼저 할수록, 곱셈은 작은 수를 먼저 할수록 이득입니다. 또한 덧셈에 들어가는 수는 곱셈에 들어가는 수보다 작아야 합니다. 이를 모두 만족하도록 수를 잘 배열해 주면 됩니다.

3월 5일

33623. Newspapers for Magicians (G2)

2026년의 265번째 문제입니다. 모든 평행우주의 베르제르그 왕국은 그 구조가 동일합니다. 따라서 웜홀은 반드시 $O-1$번 이용하는 것이 최적입니다. 이제 $a=1,b=0$일 때의 답을 먼저 구해 봅시다. 각 평행우주에 대하여 웜홀 출발점에 이르는 최단 거리를 구하면 됩니다. 한 우주에 대해서 값을 구하면 새 출발점을 제외한 나머지의 방문 여부를 초기화하고 다시 탐색하면 됩니다. 그러나 이때 거리가 짧은 점에서부터 순회해야 하므로 큐보다 우선순위 큐를 쓰는 것이 정신건강에 이롭습니다. 그렇게 구한 답을 $x$라 하면, 답은 $ax+b(O-1)$입니다.

3월 6일

7977. 크리스 마틴 (G3)

2026년의 266번째 문제입니다. 가장 적게 등장하는 문자의 등장 횟수를 $k$라고 할 때, $c$의 하한은 $k$임을 증명할 수 있습니다. 또한 $k$번 등장하는 문자를 $n$번 출력하면 유사도가 $k$가 되므로, $c=k$입니다.

3월 7일

15924. 욱제는 사과팬이야!! (G5)

2026년의 267번째 문제입니다. $A[i][j]$를 지도의 $(i,j)$에 쓰여 있는 값, $DP[i][j]$를 $(i,j)$에서 시작하여 $(N,M)$에 도달하는 경로의 수로 정의합시다. 초깃값은 $DP[N][M]=1$입니다. 이제 점화식을 세워 봅시다. $DP[i][j]$의 값은 다음과 같습니다.

• $A[i][j]$가 E일 때, $DP[i][j+1]$
• $A[i][j]$가 S일 때, $DP[i+1][j]$
• $A[i][j]$가 B일 때, $DP[i][j+1]+DP[i+1][j]$

DP 테이블을 모두 채우고 나면, 전체 테이블의 합이 답이 됩니다.

2853. 배 (S1)

2026년의 268번째 문제입니다. 먼저 배열에 등장하는 초항이 $1$인 등차수열의 공차들을 모두 저장하는 배열을 만듭니다. $1$을 제외한 배열의 원소를 앞에서부터 보면서, 지금까지 확인한 등차수열에 들어가는지 확인해 줍니다. 만약 들어가지 않는다면 새 등차수열을 만듭니다. 배열의 끝까지 보았을 때, 만들어진 등차수열의 개수가 정답이 됩니다.

3월 8일

17209. 새내기와 헌내기 (G2)

2026년의 269번째 문제입니다. 신고한 사람과 신고당한 사람을 무향 간선으로 이었을 때, 주어진 그래프가 이분 그래프가 되는 것은 쉽게 알 수 있습니다. 이제 각 연결 요소에 대해서 두 그룹의 정점 수를 각각 구해주고, 정점이 더 많은 그룹을 헌내기로 가정하면 됩니다.

3월 9일

1323. 숫자 연결하기 (G4)

2026년의 270번째 문제입니다. $N$의 자릿수를 $d$라고 할 때, 현재 수 $x$에서 $N$을 한 번 더 적는 것은 $x$를 $10^dx+N$으로 만드는 것과 같습니다. 각 작업마다 $K$로 나눈 나머지만을 저장하고, 현재까지 찾은 나머지를 기록합니다. 나머지가 $0$이 되면 그때까지 걸린 횟수를 출력해 주면 되고, 그 전에 사이클이 발생한다면 $-1$을 출력하면 됩니다.

3월 10일

17836. 공주님을 구해라! (G5)

2026년의 271번째 문제입니다. $(1,1)$에서 $(N,M)$과 그람의 위치에 도달하는 데 걸리는 최단 시간을 각각 구합니다. 두 거리를 각각 $d_1$과 $d_2$, 그람의 위치를 $(x,y)$라 하면, 공주님을 구하는 데 걸리는 최단 시간은 $\min(d_1,d_2+(N-x)+(M-y))$입니다.

3월 11일

15922. 아우으 우아으이야!! (G5)

2026년의 272번째 문제입니다. 먼저 주어진 선분들을 시작점 순으로 정렬합니다. 합친 선분을 저장하는 변수를 만들어 놓고, 선분들을 앞에서부터 순회합니다. 현재 선분이 합친 선분에 붙을 수 있다면 끝값만 갱신하고, 그러지 못한다면 선분 개수를 $1$ 더해준 뒤 합친 선분 전체를 갱신합니다. 마지막으로 남은 합친 선분까지 개수에 포함시킨 답을 출력하면 됩니다.

3월 12일

13164. 행복 유치원 (G5)

2026년의 273번째 문제입니다. $K$개의 조로 나누는 행위는 $K-1$번 분할하는 행위와 같습니다. 또한 티셔츠를 맞추는 비용은 각 조에서 키 최댓값과 최솟값의 차이이므로, 이 문제는 각 키를 수직선에 놓은 뒤 모든 점을 덮는 $K$개의 선분의 길이 합을 최소화하는 문제와 같습니다. 따라서 전체 최댓값과 최솟값의 차이를 구한 뒤, 연속된 두 키 중 차이가 가장 큰 $K-1$개를 빼 주면 됩니다.

3월 13일

2251. 물통 (G4)

2026년의 274번째 문제입니다. 각 물통의 상태를 정점으로, 물을 옮기는 행위를 간선으로 하여 그래프 탐색을 돌립니다. $(0,0,C)$에서 출발하여 $(0,x,C-x)$에 도달할 수 있을 때, $C-x$를 결과 배열에 저장합니다. 이제 결과 배열을 정렬 후 출력하면 됩니다.

3월 14일

1670. 정상 회담 2 (G3)

2026년의 275번째 문제입니다. $N=x$일 때 문제의 정답을 $f(x)$라 합시다. $N$명 중 $2$명을 골라 악수시키면, 전체 원이 $a$명과 $N-a-2$명으로 나누어집니다. 이 각각을 새로운 원으로 볼 수 있으므로, $f(x)=\sum_{i=0}^{\frac{x}{2}-1}f(2i)f(N-2i-2)$입니다. 이 점화식을 $O(N^2)$에 구현하여 답을 구하면 됩니다. $N$이 $10^4$까지 가능하지만, 상수가 작아 매우 빠르게 돌아갑니다.

3월 15일

25978. 2차원 다중 업데이트 다중 합 (G3)

2026년의 276번째 문제입니다. 모든 업데이트가 쿼리 이전에 이루어지므로, 2차원 imos법을 사용하여 간단하게 해결할 수 있습니다. 쿼리가 구간 합이므로 누적 합을 두 번 돌려야 함에 유의해 주고, 초기값은 2번 쿼리가 들어오기 시작할 때 더해 줍시다.

3월 16일

25187. 고인물이 싫어요 (G4)

2026년의 277번째 문제입니다. 각 연결 요소에 대하여 청정수가 고인물보다 더 많은지 여부를 저장합니다. 그리고 각 쿼리마다 정점이 속한 연결 요소의 답을 출력하면 됩니다.

3월 17일

16528. Highway Decommission (G1)

2026년의 278번째 문제입니다. 먼저 다익스트라로 $1$번 정점에서부터 다른 모든 정점까지의 최단 경로를 저장합니다. 이때 정점의 방문 순서를 함께 저장합니다. 다음으로, 먼저 방문한 정점부터 탐색하며 이전 정점으로 가능한 것들과의 간선 중 비용이 최소가 되는 것을 선택합니다. 마지막으로 선택한 간선들의 유지비 합을 출력하면 됩니다.

3월 18일

12892. 생일 선물 (G4)

2026년의 279번째 문제입니다. 먼저 각 선물을 비용 순으로 정렬합니다. 이제 두 포인터를 모두 맨 왼쪽에 놓고, 비용 차이가 $D$ 미만이면 오른쪽 포인터를 한 칸 뒤로, $D$ 이상이면 왼쪽 포인터를 한 칸 뒤로 옮깁니다. 이 작업을 반복하면서, 받을 수 있는 선물 집합 중 만족도 합이 가장 큰 것을 출력하면 됩니다.

3월 19일

13314. 플로이드에 오타가? (G3)

2026년의 280번째 문제입니다. 제시된 코드를 읽어보면, 올바른 플로이드와 잘못된 플로이드의 차이는 k <= N(옳은 코드)과 k < N(틀린 코드)뿐임을 알 수 있습니다. 즉 $k=N$인 경우를 고려하지 않는데, 이는 최단 경로가 $N$번 정점을 포함할 때를 고려하지 못한다는 문제를 지닙니다. 따라서 $N$번 정점에 다른 모든 정점을 매달고, 나머지 정점 간의 거리는 매우 크게 잡으면 되겠습니다.

총평

3월 20일에 스트릭이 깨져버렸고, 멘탈이 나가버리고 말았습니다. 어쩌겠습니까. 이제 4월인데 다시 해야죠.