Code Golf: Choose
코드 골프는 주어진 문제를 누가 더 짧은 코드로 푸는지 겨루는 사이트입니다. 어제 새로운 문제가 올라와서 파이썬으로 풀어봤습니다. (현재 7등, 56바이트)
이번 문제의 제목은 Choose로, 두 개의 숫자가 주어지면 조합(Combination)을 구하는 것입니다. 처음 봤을 때는 쉬울 것 같았는데, 방법이 꽤 여러가지라 생각보다 어려웠습니다.
일단 입력은 이런 식으로 주어집니다.
100, 3
다른 문제는 대부분 파이썬이 입력에서 불리했는데, 이 문제는 입력 받기가 아주 쉽습니다. 파이썬 내장 함수 중에 input이 있는데, eval(raw_input())과 동일한 결과를 냅니다. 즉, 여기에서는 (100, 3) 튜플을 돌려받는 것이죠.
이제 입력을 받았으니 계산을 해봐야겠죠? 처음에는 팩토리얼을 구현한 뒤 그걸 가지고 정석적인 방법으로 풀어봤지만, 너무 길어서 순위권 안은 도저히 무리였습니다. 그래서 재귀적인 방법이 없나 생각해보다가 그걸 사용했습니다. (아래는 의사 코드)
f(n, k) = n * f(n - 1, k - 1) f(n, 0) = 1
그게 성공한 코드 중에 가장 짧았습니다. 몇 가지 코드는 테스트에 실패했는데요, 재귀적인 방법과 같은 방식을 반복적인 것으로 풀어놨는데, int와 float의 타입 차이로 인해 1씩 오차가 생겨버려서 (2바이트 더 짧은데 ㅠㅠ) 어쩔 수가 없더군요. 무작위로 생성된 테스트 부분에서 실패하는 것도 아니라서…
대체 현재 1등인 39바이트는 어떻게 한 건지, 참 대단합니다.