구사과

5월 22일 KAIST RUN에서 봄 대회를 진행하였다. 대회는 백준 온라인 저지에서 진행하였으나 Open Contest의 경우 Codeforces Gym에서도 진행하였다.아래는 본 대회의 Scoreboard이다.ProblemsOpen Contest ScoreboardCodeforces Gym ArticleEditorialTests & Checker & Solutions

수학적 귀납법 글의 20번 문제 풀이를 적어보았다. 삼성전자 소프트웨어 멤버쉽 과제의 일환으로 써서 글이 많이 길다. 고로 PDF로 따로 첨부한다.

1. POI디스크립션을 차근차근 읽으면서, 문제의 점수, 참가자의 점수, 참가자의 등수를 문제에 적혀있는 그대로 계산하면 됩니다. 2. 내일 할 거야문제를 쉽게 변형해서, 과제 리스트가 주어졌을 때 모든 과제를 마칠 수 있는지를 yes / no로 판별하는 문제를 생각해 봅시다. 이 경우 과제를 데드라인 순으로 정렬한 후 처리하는 그리디 알고리즘이 최선임을 증명할 수 있습니다. (데드라인이 큰 것을, 데드라인이 작은 것보다 먼저 처리할 이유가 없음) 한편, T일 쉰다는 것은, 사실 모든 데드라인을 T일 앞당긴 후 과제를 시작한다는 것과 동치입니다. 고로 과제를 하는 순서가 바뀌지 않습니다. 실제 T를 구하는 것은 과제를 역순으로 보면서 할 수 있습니다. 3. Archery Tournament원은 빠르게 다..