별사탕와쟉와쟉

총 12문제 중, 난이도 순서대로 H, I, L, D, F, K를 풀어보자. H - Needle 벽이 1 간격으로 세 레이어가 있는데, 각 벽에는 구멍이 나있다고 한다. 각 벽의 구멍 위치가 주어졌을 때, 바늘이 지나갈 수 있는 경우의 수를 구하라는 문제다. 구멍의 개수는 한 줄당 최대 5만개, 위치값은 -30000부터 30000의 정수이다. 전체탐색하면 위쪽 벽 50000개, 아래쪽 벽 50000개를 조합해 평균값을 내고 그 값을 가지는 중간 벽 구멍이 있으면 풀 수 있지만 50000*50000 = 2.5x10^9이므로 시간 초과가 난다. n^2이 아닌 nlogn으로 풀어야 한다. 키포인트 위쪽 벽과 아래쪽 벽 위치 값을 평균낸다는 아이디어를 재활용하자. 총 60001개의 위치가 가능하므로 구멍의 위치..

교수님께서 알고리즘 수업을 수강한 학생 중 1~2학년이고 성적 잘 받은 사람 중에서 ICPC 나가는걸 제안해 주셨다. 그래서 어느샌가 팀이 꾸려졌고 올해 ICPC에 출전하게 되었다... 교수님께서 내 주신 첫 과제는 ICPC 2020 Seoul Regional 세트 풀어오기 이다. 백준 OJ에 문제세트 카피가 있으며 쉬운 문제부터 풀어보려 한다. 문제 난이도는 solved.ac에 등재된 것을 기준으로 한다. 총 12문제 중, 난이도 순서대로 B, E, C, G, J, A의 풀이를 적는다. B - Commemorative Dice 간단한 문제다. 경우의 수가 6x6=36가지밖에 없으므로 이기는 횟수를 카운트해 확률을 출력하면 된다. 다만, 기약분수로 출력해야 하므로 GCD를 한 번 돌려 주자. 코드 더보기..