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

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

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

쉬운 문제 설명만 하면 제법 지루한 법이다. 그래서 가능하면 적어도 다섯 문제마다 한 번씩은 Silver V 이상의 난이도를 가진 문제의 풀이를 올리려고 한다. 풀이가 부족하지 않게 나도 빨리빨리 질주해야겠다. 그럼 22년 11월 10일의 마지막 포스팅, 줄어들지 않아. 무려 Silver I 난이도의 문제, 본격적으로 풀이에 돌입해 보자. 문제 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다. 예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다. 이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다..