수요가 많은 글이 어려운 문제의 해설이 아니라 적당한 난이도의 문제 해설이라는 것을 알고 최근 글을 둘러보았다. 문제 해설 글이 점점 줄어지기도 했거니와 내가 어렵게 풀어서 임팩트가 강하게 남은 문제들만 해설을 남기는 것 같은 기분이다. 분명 처음 블로그를 개설했을 때는 전혀 안 이랬는데... 실력이 는다고 자만했나? 그래서 과거 푼 문제를 뒤져보다가 굉장히 교육적이고 추천할 만한 문제를 발견해서 그 문제의 해설을 작성하려고 한다. 지난 해 ICPC 인터넷 예선의 예비소집 문제이기도 하고, 재작년 ICPC 인터넷 예선 문제이기도 하다. 퀄리티는 보장이 되어 있다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 \(n\)개의 선물 가격이 주어졌을 때, \(b\)의 예산으로 최대로 많은 선물을 사려고 한다. 이..

이번 주는 각종 대회들로 가득 찬 한 주였다. 목요일에는 Zero One 오픈 콘테스트, 금요일에는 GBS 오픈 콘테스트, 토요일에는 제1회 미적확통컵까지... 가장 높은 점수를 챙긴 것이 제1회 미적확통컵이었다. 그 중에서 조금 풀이과정이 기발하고 과정이 비자명한 문제를 가지고 왔다. H번 문제, 방향 정하기이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 n개의 점이 있다. 어떤 두 점을 잡더라도 항상 하나의 간선으로 이어져 있도록 간선이 총 \(\frac{n(n-1)}{2}\)개 있다. 조건을 만족하도록 모든 간선들에 방향을 정해주는 방법의 수를 구하자. 조건: 각 점에서 출발해서 간선 방향을 따라 어떻게 이동해도 출발한 점으로 돌아올 수 없다. 입력 첫 번째 줄에 n이 주어진다. (2 ≤ n ≤ ..

그간 격조했다. 아직 공대생 신분이기 때문에 기말고사는 피할 수 없는 재앙과도 같다. 다음 학기 장학금을 타 쓰기 위해서라도 시험공부를 게을리 할 수는 없다...! 이 문제는 어제 개최된 개인 대회 겨울 숲의 초대 C번 문제이다. 수학을 좀 아는 사람과 수학을 좀 모르는 사람 사이 체감 난이도 차가 극심한 문제. 개인적으로 연구하던 컴플리트 가챠와 구조가 완전히 동일해서 아주 쉽게 풀었다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 겨울 나라의 왕은 꽃을 좋아하는 왕비를 위해 가장 아름다운 꽃들을 모아 화관을 만들기로 했다. 왕비가 좋아하는 꽃들은 특별해서 마법의 씨앗을 심은 뒤 별빛을 받아야 피어난다. 마법의 씨앗에서 피어날 수 있는 꽃들의 종류는 \(N\)가지이며, 각 종류의 꽃들이 피어날 확률은 동..

어렵다고 꼭 고급 테크닉을 사용하는 문제일 리 없고, 고급 테크닉을 사용한다 하더라도 생각보다 쉬운 문제일 수 있다. 특히 고급 테크닉을 사용하는 기본이 되는 문제라면 더욱. 잘못 말리면 끝까지 못 풀 수 있지만 해법을 알게 된다면 생각보다 순식간에 풀 수 있는 문제이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)..

이 문제는 UNIST 대회인 Uni-CODE 2022의 B번 문제이다. 대회 때 완벽하게 풀어 낸 유일한 문제이다. A번은 어떻게 푸는지 감도 못 잡겠더라. 정해가 빨리 공개되면 좋겠다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 외계인 윤이는 지구를 정복하고자 세계의 중심 도시인 울산을 침략했다. 울산에는 N개의 빌딩이 일렬로 늘어서 있고, 왼쪽에서 i번째 건물의 높이는 \(h_i\)이다. 윤이는 울산을 파괴하기 위해 다음과 같은 계획을 세웠다. 윤이는 매일 UFO를 타고 울산의 상공을 가르며 가장 높이가 높은 빌딩에 레이저를 발사할 것이다. 레이저에 맞은 빌딩은 높이가 1 낮아진다. 만약 그 날에 가장 높이가 높은 빌딩이 여러 개라면, 해당하는 모든 빌딩에 레이저를 발사한다. 만약 이미 모든 빌딩의 ..

수학적으로 접근할 수 있는 문제는 먼저 수학으로 접근해 보아야 한다. 런타임 전의 전처리를 뇌로 하는 것이다. 인간의 뇌라고 특별할 게 있겠는가. 돌발상황에 아주 잘 대처하는 거대한 생체 컴퓨터인 것을. 머리로 계산하고 코드를 단순히 짜는 게 오히려 더 낫다(고 한다). 주석만 적당히 달려 있다면. 물론 기본기가 어느 정도 되어 있다는 전제 하에 말이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 1..