리유나의 항해일지

작년에 ACM-ICPC 대회에 출전했던 적이 있었다. 내가 참가했던 팀은 5개 해결로 전체 80등 언저리로 본선 진출에는 실패했었는데, 올해에 다시 이 대회에 나가려고 생각을 하고 있다. 그 과정에서 작년에 제일 고민을 많이 해봤었던(그렇지만 결국 풀지는 못했던)Parcel 문제를 다시 떠올리게 되었고, 1년만에 문제에게 복수를 하러 가보려고 한다. 문제는 여기서 볼 수 있다. 쉽게 말해서 뒤에 주어진 정수들 중에서 4개 골라서 앞에서 주어진 정수를 합으로 되게 만들 수 있냐는 문제이다. 이런 문제에서 흔히 생각할 수 있는 방법은 다음과 같다. 1. 완전 탐색. 주어진 거 4개씩 고르는 경우를 다 찾아보면 된다. 구현은 재귀적으로 대충 하면 될 거 같다. 그러나 n이 5000개까지 가능하다. 4개씩 다 ..

2001년 ACM ICPC 예선으로 나왔던 문제입니다. 문제는 여기서 확인할 수 있습니다. 고등학교 2학년 때였나, 특이한 정보과학 과목을 수강했던 적이 있었습니다. 선생님께서 마지막에 문제 24개를 주시면서 여기서 95% 이상을 풀면 시험 성적에 관계없이 A+을 주겠다고 하셨던 적이 있는데, 그 중 한 문제로 처음 접했던 기억이 납니다. 처음에 이 문제를 봤을 때는 DP(동적계획)와 같은 방법을 사용해서 재귀적으로 풀어야 하나 하고 고민했지만, 이런 시도가 언제나 그렇듯이 잘 되질 않았습니다. Brute Force(완전탐색)으로 해볼까도 생각해봤는데, 아무래도 m+n이 10 이상 30 미만인데 30이면 전체 가능한 경우의 수가 2^30(≒10^9)정도로 조금 무리인 감이 있습니다.(게다가 저게 되는지 ..