2026. 1. 27. 02:27ㆍMassive Chunk
최근 꽤 많은 수의 Unrated를 풀고 첫 기여를 매겼다. 개중에 블로그에 풀이를 올리고 싶었던 것도 있고 아닌 것도 있는데, 첫 기여라 사람들이 많이 찾으면 난이도가 크게 변동될 가능성이 농후한 문제들이 여럿 보여서 그냥 Massive Chunk라는 카테고리를 만들고, 코드 없이 간단하게 풀이 스케치만 올리기로 했다.
정말 야생의 문제가 많았다. 난이도 자체를 가늠하지 못하기 때문에 풀지 못하고 문제 본문만 본 채 넘기는 문제가 많은 건 당연하다. 하지만 입력 형식이라던지, 예제의 상태라던지, 심지어는 제한을 제대로 안 주는 문제도 여럿 있었다. 반면교사로 삼기로 했다. 문제의 난이도나 알고리즘 유형이 아닌 곳에서 내가 풀다가 불쾌해지는 지점이 어디에 있는지 알았으니, 추후 문제를 낼 때는 저런 요소를 배제할 수 있을 것이다.
특이한 점은 AI(혹은 그를 이용한 사람)가 푼 문제가 제법 된다는 거였는데, 이걸 또 나중에 천천히 생각해 보니 아무래도 저런 문제들을 찾아 푸는 사람은 없지만 자동화 봇은 그냥 가능한 거 다 제출할 테니 당연히 AI 비중이 높아지지 않을까 하는 결론이 나왔다. AI가 푼 문제 중 일부는 나도 풀 수 있다는 생각을 하고 있었는데, 인간의 무력함을 어느 정도 느끼기도 했다.
solved.ac 티어는 내 기여 기준이다. 실제 티어와 다를 수 있다. 어느 정도 풀 가치가 있어 보이는 문제는 (추천!)으로 표시한다. 좋은 문제라기보다는 이 난이도를 풀 실력의 사람에게 연습이 될 만한 문제를 골라 추천한다.
BOJ 11521 - Romance of The Three Kingdom : G2 (추천!)
플러드 필로 세 개의 왕국을 구분한 뒤, A-B-C의 형태로 연결시킬지 아니면 바다 한가운데에 하나의 hub를 띄워서 세 왕국과 각각 연결시킬지를 결정하자. RC가 생각보다 작아서 이래도 충분히 돈다.
BOJ 15375 - Friday : S5
그대로 datetime을 쓰면 안 된다. \(N=10^{15}\)일 때의 답이 무려 19165349050932년 7월 11일이고, datetime을 그냥 사용하면 반드시 터진다. 기준일로부터 \(N\)주 후의 시간을 구하는 것이고, 윤년 여부는 400년 주기를 가질 테니 2800년이 \(x\)주와 같은 \(x\)를 찾아주면 된다.
BOJ 9380 - Blast the Enemy! : G2
다각형의 centroid를 구하는 문제이다. 이는 다각형을 삼각분할한 뒤, 각 삼각형의 centroid의 가중치를 그 삼각형의 넓이로 두고 가중평균을 구함으로서 얻을 수 있다. 문제에 formal definition이라고 이중적분 식을 줬는데, 왜 줬는지는 모르겠다.
BOJ 29971 - Murdude lahutamine : S5
두 분수의 차이를 구하기만 하면 되는 간단한 문제인데, 출력의 일부가 대분수 아스키 아트 형식으로 되어 있다. 실수할 여지가 산재해 있으므로 케이스를 잘 나눠서 요구하는 대로 출력해 주면 맞는다.
BOJ 29520 - Дерево : G5
0번 정점이 루트인 트리에 대해, 자식으로부터 들어오는 붉은 간선이 최대 하나이도록 붉은 간선을 적절히 칠하는 문제이다. 자식으로부터라는 제한 조건이 있으므로 각 노드에 대해서 자식의 수에 1을 더한 만큼의 경우의 수가 가능하다. 아예 붉은 간선을 안 칠할 수도 있으니.
BOJ 29394 - Суммы : S3
\(a\)부터 \(b\)까지의 수가 나오는 빨간 주사위와 파란 주사위 두 개를 던져, 나온 수의 합이 \(c\) 이상 \(d) 이하가 나오는 경우의 수를 구하는 문제이다. 잘 해석하면 등차수열의 합 공식 여러 개를 이용하여 풀 수 있다.
BOJ 8263 - Inwazja kosmitów : G4 (추천!)
최악의 경우 이웃한 도시는 습격당할 수 없고, 인접한 두 습격당한 도시 간 거리가 4이면 양쪽 사이에 이웃하지 않은 다른 도시 하나를 추가로 더 습격할 수 있으므로 이런 경우는 최악이 아니다. 따라서 인접한 두 습격당한 도시 간 거리는 반드시 2 혹은 3이다. 이제 DP를 돌리면 끝.
BOJ 29643 - Поддеревья : P5 (추천!)
트리에서 k개의 서브트리를 겹치지 않게 고르는 경우의 수를 구하는 문제다. 생성 함수로 풀 수 있다고 생각했다가 크게 얻어맞았고, 꽤 골치아픈 \(\mathcal O(N^3)\) 트리DP로 풀었다. 루트를 임의로 잡고, 현재 정점의 부모가 같은 서브트리에 있는 경우와 없는 경우로(즉, 확장 불가능성과 가능성으로) 상태 두 개를 잡았다. 꽤 어려웠고, 추천하고 싶은 문제.
BOJ 29459 - Фотография : S4
일부가 가려진 날짜와 날짜의 구간이 주어진다. 적당히 가려진 부분에 숫자를 집어넣었을 때 구간 안에 몇 개의 날짜가 들어갈 수 있는지 묻는 문제이다. 그냥 적당히 채워넣어서 브루트포스를 돌리면 된다. 제한 상으로 1970년부터 2038년까지만 가능하다고 하므로 경우의 수가 크게 준다.
BOJ 29358 - Поймать Халка : B2
\(N\)차원 직사각형 모양 얼음 안에 \(N\)차원 직사각형 모양 헐크가 들어 있다. 헐크를 해방시키기 위해서 칼질을 몇 번 해야 하는지 묻는 문제다. 이미 드러난 면의 갯수를 따지면 쉽게 풀 수 있다.
BOJ 29972 - Lauamäng : S1
원형 보드게임판에서 일부 칸에 강제 이동이 부여되어 있다. 이 때 절대 밟을 수 없는 칸을 판별해내는 문제다. 그냥 강제 이동이 부여되어 있지 않은 칸에는 1~6칸 앞의 칸으로 가는 간선을 부여하고 그래프 탐색을 해 주면 된다.
BOJ 29190 - Стражи : B3
그냥 맨해튼 거리가 일정 이하인 점을 브루트포스로 찾아 주면 된다.
BOJ 32696 - Avaldis : B3
\(Ax+B\)를 출력해 주면 된다. 계수가 0인 항은 지워 버리고, \(x\)의 계수가 \(\pm1\)일 때 처리를 따로 해 줘야 하는 등 케이스를 이 난이도에서 유의미하게 나눈다.
BOJ 4152 - New Horizons : P5
이상한 기하문제 그1. 구면삼각법을 요구한다. 정확하게는 위도 경도가 주어진 두 점 사이의 각거리를 구해야 한다. 두 점 사이의 각거리가 지평선 시야각의 합 이하인지를 판별하는 문제. 이런 거 보면 구면삼각법이 PS 범위가 맞다.
BOJ 9165 - Nested Shrubbery Boxes : G5
박스가 다른 박스 안에 들어갈 수 있는지 판별하는 것은 쉽고, 그렇다면 문제는 LIS 문제로 환원된다.
BOJ 5653 - Elias Omega Coding : B1
하라는 대로 하면 되는 2진법 구현 문제. 이런 게 실제로 있는지는 잘 모르겠다.
BOJ 8054 - Promotion : G4
이중 우선순위 큐를 구현하거나, C++의 multiset을 쓰거나. 매일 가장 비싼 것과 싼 것을 하나씩 뽑아서 제거하는 것이므로.
BOJ 8014 - Island : G3 (추천!)
원형 배열은 arr+arr로 선형처럼 쓸 수 있다. 이제 투 포인터로 \(L/2\)에 가장 가까운 부분합을 찾아주면 된다.