14889. 스타트와 링크
사람은 총 N명, 최대 20명 이를 순열로 늘어 놓아서 앞에는 스타트팀, 뒤에는 링크팀으로 하면 중복계산도 상당히 많고, 총 경우의 수는 20! = 상당히 큰 수이다 >>>>>>>>>>>> 1억 당연히 시간초과가 난다. 문제를 풀면서 자연스럽게 생각할 수 있는 것은 사실 조합이다. 20C10 는 10! 보다 작을 것이라는 것을 예측할 수 있는데 실제로 그 결과는 10!(3백만)보다 훨씬 작다. 18만정도이다. 여기에 각 팀 스코어를 계산해야하는 시간이 (N/2) x (N/2) 이므로 100이라고 하면, 1800만 < 2초 안에 가능하다. 내가 맨 처음에 한 것은, 예를들어 1, 2, 3을 뽑았으면 총 1, 2, 3, 4, 5, 6 인 set에서 1, 2, 3을 뽑는 것이다. 즉 4, 5, 6을 만드는 것..
2019. 9. 21.
