- 이 글에는 문제의 풀이가 모두 공개되어 있습니다. (코드 미포함) 스포일러에 주의하세요.
- 문제는 번호 순서로 적혀 있으며, 제목 옆의 난이도는 푼 날짜를 기준으로 합니다.
2025년이 끝났습니다. 연말에는 역시 백준이죠. 이번 달에는 51개의 문제를 풀었습니다. 22일에 GSHS X SASA 연합 대회에 출전했는데, 제 개인 아이디로 푼 문제가 아니므로 제외했습니다.
푼 날짜: 20251205
작은 상자의 크기가 일 때 최대로 넣을 수 있는 개수를 라고 하면, 이 함수는 에 대한 감소함수입니다. 따라 이분 탐색을 실수에서 적용하여 문제를 해결할 수 있습니다. 초기 범위는 로 하고, 100회 정도 이분 탐색을 하면 허용하는 절대/상대 오차가 이므로 충분히 오차 범위 내에 들 수 있습니다.
푼 날짜: 20251221
Ray Casting 등의 방법으로 다각형 내 점 판정을 에 하면 되는 문제입니다. 반직선이 다각형의 꼭짓점을 지날 때, 점이 다각형의 변 위에 있을 때와 같은 경우를 주의해 줍시다.
푼 날짜: 20251231
2차원 누적 합을 사용하거나, 브루트 포스를 하면 되는 문제입니다. 제한이 빡빡하기는 하지만 가 가능하다고 합니다. 10번 넘게 틀린 문제이기도 한데, long long int 변수에 %d로 입력을 받아 그랬습니다.
푼 날짜: 20251222
앞선 1688번 문제가 오목 다각형 내부의 점 판정 문제라면, 이 문제는 볼록 다각형 내부의 점 판정 문제입니다. 주어진 담 기둥의 컨벡스 헐을 구하고, 내부에 가 있는지 에 판정합니다. 구체적인 알고리즘은 생략하겠습니다. 가 컨벡스 헐 내부에 있으면 컨벡스 헐을 이루는 점들을 제거하고, 없으면 반복을 종료합니다. 제거한 컨벡스 헐의 개수가 정답이 됩니다.
푼 날짜: 20251229
1번 정점을 루트로 잡고, 를 다음과 같이 정의합시다.
: 번 정점이 얼리 어답터가 아닐 때 를 루트로 하는 서브트리에서 최소 얼리 어답터 수
: 번 정점이 얼리 어답터일 때 를 루트로 하는 서브트리에서 최소 얼리 어답터 수
번 정점의 자식이 일 때, 과 의 점화식은 다음과 같습니다.
만약 번 정점이 리프라면 부분을 0으로 놓고 구하면 됩니다. 이것을 재귀, 즉 DFS로 구현하면 AC를 받습니다.
푼 날짜: 20251230
두 경찰차가 마지막으로 해결한 사건이 각각 번, 번 사건인 시점에서 시작하여, 모든 사건이 해결될 때까지 필요한 최소 이동 거리를 라 합시다. 단, 초기 위치에 있을 때는 또는 가 0인 것으로 합니다. 일 때, DP 점화식은 아래와 같습니다.
이것을 재귀함수로 구현해 주고 (바텀업으로 하면 구현이 힘들어집니다), 각 함수 호출에서 이후 상태 2개 중 최적인 것을 별도 배열에 저장해 주면 역추적까지 할 수 있습니다.
푼 날짜: 20251226
우선순위 큐를 이용하는 대표적인 문제입니다. 현재까지 입력받은 원소 중 큰 절반은 최소 힙에, 작은 절반은 최대 힙에 넣는 것이 핵심입니다. 입력받은 원소가 홀수 개일 때는 둘 중 하나의 원소 개수가 더 많게 되는데, 저는 최대 힙의 원소 개수가 더 많게 하였습니다. 새로운 원소가 들어왔을 때, 힙에 넣는 방법은 아래와 같습니다.
최소 힙에는 언제나 상대적으로 큰 원소들이, 최대 힙에는 작은 원소들이 들어간다는 것을 알 수 있습니다. 홀수 번째 원소를 넣은 뒤 최대 힙에 있는 원소의 최댓값을 읽어주면 전체 원소의 중앙값이 됩니다.
푼 날짜: 20251229
먼저 중복되는 를 없애줍시다. C++의 map이나 Python의 dict를 활용하여 Key에는 의 값을, Value에는 등장 횟수를 저장합니다. 이제 map을 순회하면서 문제에서 제시된 함수를 직접 수행합니다. 최악의 케이스는 인 경우일 텐데, 조화급수의 성질에 의해 의 시간 복잡도가 됩니다. 의 누적합으로 쿼리를 처리할 준비를 하고, 각각의 쿼리를 수행하면 됩니다.
푼 날짜: 20251231
이분 탐색과 누적 합을 이용하여 풀었습니다. 두 수열을 각각 와 라 했을 때, 의 각 원소에 대해 에 해당 원소가 있는지 lower_bound로 구합니다. 또한 각 수열의 누적 합을 저장해 놓습니다. 모든 교차점을 얻은 뒤에는 누적 합으로 각 구간의 합을 구해 최댓값을 택합니다.
푼 날짜: 20251224 (자정 넘김)
이 글을 참고하세요.
푼 날짜: 20251224 (자정 넘김)
이 글을 참고하세요.
푼 날짜: 20251206
의 제한이 작으므로 모든 경우의 합을 직접 계산해 보면 됩니다. 계산 결과 같은 수가 여러 번 나오는 것은 한 번만 세어야 하므로 중복을 제거하는 자료 구조를 사용해 줍시다.
푼 날짜: 20251212
높이 의 2 타워 값을 라 합시다. 이므로 일 때의 답이 2임은 자명합니다. 인 경우, 잘 생각해 보면 답이 항상 1이라는 것을 알 수 있습니다. 증명은 아래와 같습니다.
라면 으로 나타낼 수 있습니다. 따라서 은 로 나타낼 수 있습니다. 부분을 다시 전개하고, 이를 반복하면 이 을 인수로 가진다는 것을 확인할 수 있습니다. 결과적으로 은 3의 배수이고, 를 3으로 나눈 나머지는 1이 됩니다.
푼 날짜: 20251214
덱을 이용하는 기초 문제입니다. 사용한 기술을 뒤에서부터 보면서 카드를 다시 더미에 넣는 것을 생각해 봅시다. 각 기술의 역연산은 다음과 같습니다.
더미를 덱으로 나타내어 구현해 주면 됩니다.
푼 날짜: 20251208
조합론 문제 같아 보이지만, DP로 쉽게 풀리는 문제입니다. 먼저 물벼룩의 생존 확률에 을 곱한 것은 생존하는 경우의 수와 같음을 확인합니다. 다음으로 를 다음과 같이 잡읍시다.
임은 쉽게 알 수 있습니다. 또한 초기 조건은 입니다. 이를 올바르게 구현하면 문제를 해결할 수 있습니다.
푼 날짜: 20251229
상사-부하 관계는 트리임을 어렵지 않게 알 수 있습니다. 각 사람이 초기에 받은 칭찬의 양을 기록해 두고, 루트인 1번 정점에서부터 DFS 또는 BFS를 돌리면서 누적 합을 해주면 됩니다.
푼 날짜: 20251211
분리 집합으로 풀면 오히려 어렵고, 스위핑을 사용하는 문제입니다. 먼저 주어진 범위를 시작점 순으로 (시작점이 같으면 끝점 순으로) 정렬해 줍시다. 다음으로 범위를 저장한 배열을 순회합니다. 번째 범위와 번째 범위 사이의 관계는 다음 2가지가 가능합니다. 번째 범위의 시작점을 , 끝점을 라 합니다.
합쳐진 방의 개수는 1로 하여 방의 개수를 구해주면 답이 됩니다.
푼 날짜: 20251210
와 의 제한이 작습니다. 따라서 의 2차원 배열을 만들 수 있습니다. 입력을 받으면서 2차원 배열에 블록이 쌓인 형태를 기록해 줍시다. 그 다음 높이 1부터 까지 보면서 빗물이 고이는 영역을 계산합니다. 해당 높이에 블록이 한 개 이하 있다면 고이는 영역은 0이고, 2개 이상이라면 이 영역의 개수가 됩니다.
푼 날짜: 20251229
트리 DP 기본 문제입니다. 루트 정점에서 시작하여 DFS를 도는데, 함수가 한 번 끝날 때마다 현재 정점을 포함한 서브트리의 정점 개수를 반환하게 하면 됩니다. 별도의 배열을 만들어 이 값들을 저장해 주고, 쿼리마다 답을 반환하면 됩니다.
푼 날짜: 20251216
앞에서부터 문자열 pPAp가 있는지 검사하면 됩니다. 번째 인덱스를 보고 있다면, 번째 글자부터 번째 글자까지의 문자열을 검사합니다. pPAp라면 에 4를 더하고, 그렇지 않으면 1을 더합니다. 문자열 길이만큼의 범위를 넘기 전까지 반복합니다. 최종적으로 pPAp의 개수를 출력합니다.
푼 날짜: 20251218
범위가 매우 작으므로, 문제에서 하라는 대로 해주면 됩니다. 여기에서는 어떻게 하면 하라는 대로 잘 할 수 있는지 정리합니다.
이렇게 하면 문제를 해결할 수 있습니다.
푼 날짜: 20251228
비해석적 기하학이 PS에서 요구되는 사항과 현저히 멀다는 이유로 NR을 받았다가, 최근에 NR에서 해제된 문제입니다. Euler's Theorem in Geometry를 사용하면 되는 문제이고, P4의 난이도는 순전히 증명 때문에 붙었습니다. 답은 입니다.
푼 날짜: 20251223
BFS 문제인데, 이동하는 물체가 여러 칸을 차지하는 경우입니다. 일반적인 BFS와 똑같이 구현하되, 물체가 움직이면서 새로 차지하게 되는 칸 전부에 대해 벽 검사를 해주도록 합시다.
푼 날짜: 20251224 (자정 넘김)
기준선이 1일 때부터 일 때까지 각각의 경우에 대하여 홍팀과 청팀에서 힘의 최댓값을 찾읍시다. 각 팀에 대해 순차적으로 (홍팀은 순행, 청팀은 역행) 찾아주면 에 모든 기준선에서 힘의 최댓값을 찾을 수 있습니다. 이제 각 기준선에서 어느 팀이 이기는지 알 수 있으므로, 홍팀과 청팀 중 이기는 경우가 많은 것을 출력하면 됩니다. 이기는 횟수가 같나면 X를 출력합니다.
푼 날짜: 20251225
문제에서 주어진 그래프는 아래 조건을 만족합니다.
트리이기 때문에 경로가 유일하고, 따라서 BFS나 DFS를 통해 리프 노드의 거리 최댓값을 구할 수 있습니다. 다익스트라 알고리즘을 사용해도 시간 내에 풀 수 있습니다. 저는 다익스트라로 풀었습니다.
푼 날짜: 20251231
팰린드롬이면서 수미상관인 문자열을 찾으면 됩니다. 한 문자가 번 반복되는 문자열은 매우 자명하게 팰린드롬이면서 수미상관입니다. 따라서 아무 알파벳 소문자를 번 반복해 출력하면 됩니다. 이것을 찾기 위해 밤새 연구하는 시철이는 대체...
푼 날짜: 20251231
부터 까지 내림차순으로 정렬한 수열과 부터 까지 내림차순으로 정렬한 수열을 생각합시다. 이 둘을 번갈아 가며 출력하면 AC를 받을 수 있습니다.
푼 날짜: 20251231
입력받은 문자열을 라 할 때, 한 글자가 번 등장하는 경우를 모두 고려하려면 정답의 길이가 이상이어야 합니다. 그런데 길이 의 문자열을 개의 문자 단위로 끊어서 각 부분이 한 글자를 담당하도록 할 수 있으므로, 보다 긴 문자열이 필요하지 않습니다. 따라서 출력하는 문자열의 길이는 이고, 구체적으로는 입력받은 문자열을 번 반복해서 출력하면 됩니다.
푼 날짜: 20251215
시험 기간 이슈로 날먹을 하기 위해 푼 문제입니다. 가 보다 작은 자연수이고 가 아님이 보장되므로, 아래 두 가지 경우로 나눌 수 있습니다.
이대로 구현하면 정답을 받을 수 있습니다.
푼 날짜: 20251213
naive한 경우를 먼저 생각해 봅시다. 명의 플레이어가 한 번씩 결투를 하는 것을 직접 구현한다면 시간 복잡도는 당연히 이 됩니다. 문제를 풀기에는 매우 큰 시간 복잡도죠. 여기서 이런 생각을 해볼 수 있습니다.
약수-배수 관계에 있는 플레이어들끼리만 결투를 시킬 수는 없을까?
고맙게도 문제에서 의 상한은 100만이며, 중복이 없습니다. 각 에 대해서 100만 이하의 의 배수를 찾고, 그중 배열 에 있는 것에 대해 점수 변동을 하면 어떻게 될까요? 이것이 시간 내에 돌아간다는 것을 보이기 위해 실제보다 더 큰 조건을 생각해 봅시다.
의 제한이 10만이 아닌 100만이고, 인 경우입니다. 각 에 대해서 100만 이하의 의 배수를 도는 시간 복잡도를 생각해 봅시다. 연산 횟수는 입니다. 이 크기 때문에 이를 로 근사하면 연산 횟수는 점근적으로 이 됩니다. 실제 문제의 제한은 앞서 가정한 경우보다 작으므로, 동일한 방법으로 문제를 해결할 수 있습니다.
푼 날짜: 20251231
빨랫줄을 기준으로 망토를 반으로 접는 것까지 가능합니다. 따라서 이고 이거나, 이고 이면 YES를 출력합니다. 그렇지 않으면 NO를 출력합니다.
푼 날짜: 20251207
먼저 일 때를 생각해 봅시다. 이므로 세림이에게 번 기념품을, 성주에게 번 기념품을 주면 주어진 조건을 만족합니다. 로 하여 계속 반복하면 쉽게 해결할 수 있습니다.
이제 일 때입니다. 위의 경우에서 로 바꾸어 생각해 봅시다. 그러면 남는 피보나치 수는 입니다. 즉 이므로 세림이에게 1번 기념품, 성주에게 2번 기념품을 주고 남은 기념품은 일 때와 동일하게 처리하면 됩니다.
마지막으로 일 때를 봅시다. 번부터 번까지의 기념품을 문제의 조건에 맞게 남김 없이 배분할 수 있다는 것은 이 짝수라는 것과 동치입니다. 이면 남김 없이 배분 가능하므로 은 짝수인데, 이므로 은 홀수입니다. 따라서 개의 기념품을 모두 배분하는 것은 불가능하고, 2번 기념품부터 시작하여 일 때와 동일하게 처리하면 됩니다.
푼 날짜: 20251217
과 의 중점이 전자기기의 무게 중심이라는 것은 쉽게 알 수 있습니다. 이 질량 중심의 좌표를 라 하고, 아래 두 가지 값을 생각해 봅시다.
은 원점과 질량 중심 사이의 거리, 는 질량 중심과 한 꼭짓점 사이의 거리입니다. 라면 전자기기를 회전하여 원점을 포함시킬 수 있는 것이므로 당연히 손에 닿습니다. 라면 을 만족할 경우 손에 닿습니다. 이것을 적절히 구현해 주면 됩니다. 좌표값의 범위가 작아 실수 오차는 걱정하지 않아도 됩니다.
푼 날짜: 20251229
단순히 입력받은 두 값을 곱해주면 되는 문제입니다.
푼 날짜: 20251230
는 의미가 없고, 를 출력하면 됩니다.
푼 날짜: 20251224 (자정 넘김)
이 글을 참고하세요.
푼 날짜: 20251220
층수를 세는데, 13번을 쓰지 말아야 하는 문제입니다. 입력이 12 이하이면 그대로 출력하고, 13 이상이면 1을 더해주면 됩니다.
푼 날짜: 20251229
답은 입니다. 증명은 생략합니다.
푼 날짜: 20251230
는 의미가 없고, 를 출력하면 됩니다.
푼 날짜: 20251218
문제를 잘 읽어 보면, 을 제외한 다른 정보는 필요하지도 않다는 것을 알 수 있습니다. 카트가 왕복하므로 을 출력하기만 하면 됩니다.
푼 날짜: 20251230
이면 yes, 아니면 no를 출력하면 됩니다.
푼 날짜: 20251204
승차 요금을 알 수 없다면 ?를 출력하는 것은 페이크고, 입력에서 주어진 두 역명이 같은지만 검사하면 됩니다. 같으면 0, 다르면 1550입니다.
푼 날짜: 20251209
질문에 대한 정답이 모두 주어져 있는 가장 단순한 형태의 쿼리 문제입니다. 조건 분기를 잘 해 주면 됩니다. 저는 경기과학고등학교를 더 사랑합니다. 감사합니다.
푼 날짜: 20251230
입력의 첫 글자에 따라 조건 분기를 해 주면 됩니다.
푼 날짜: 20251224 (자정 넘김)
이 글을 참고하세요.
푼 날짜: 20251227
식을 잘 정리하면 이 답이 됨을 쉽게 알 수 있습니다.
푼 날짜: 20251224 (자정 넘김)
이 글을 참고하세요.
푼 날짜: 20251230 (자정 넘김)
이면 Oh My God!을, 아니면 Success!를 출력하면 됩니다.
푼 날짜: 20251227
이 글을 참고하세요.
푼 날짜: 20251227
이 글을 참고하세요.
푼 날짜: 20251227
이 글을 참고하세요.