6591
-
백준 6591번 이항 쇼다운 :: 마이구미알고리즘 풀이/수학 2017. 9. 30. 23:50
이 글은 백준 알고리즘 문제 6591번 "이항 쇼다운" 을 풀이한다.조합에 관련된 시리즈 문제 중 하나이다.문제는 쉬워보이나 굉장히 낮은 정답 비율을 통해 만만치 않다는 것을 알 수 있다.6591번 - https://www.acmicpc.net/problem/6591 n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까? 문제의 설명에서 조합의 정의에 대해 그대로 명시했기 때문에, 조합 문제인 것을 알 수 있다.다른 관련 문제들은 단순한 접근 또는 동적계획법을 통해 해결할 수 있다.하지만 이 문제는 다르게 접근해야한다. 우리는 실제로 수학 문제를 풀 때, 1번을 이용해서 조합 문제를 해결한다.다음과 같이 풀 수 있다. 10C4 => (10*9*8*7) / (4*3*2*1)10C3 =>..