백번 열번 백번 열번

11051

• 백준(BOJ) 11051번 이항 계수 2

  알고리즘 풀이/백준(Boj) 2019. 7. 30. 01:27

  문제 : https://www.acmicpc.net/problem/11051 문제자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 나의 풀이: 이항계수(N, K) 를 구하는 방법은 (N-1, K-1) + (N-1, K) 이고 재귀적으로 호출해주면 된다. 하지만 N이 1000이기에 시간내에 풀기에는 불가능하다. ex ) 이항계수(5, 2)를 예로 이항계수(4,1) 부터 쭉 재귀적으로 내려가서 답을 구한 다고 가정하면 또 (4,2)를 구할 때에도 (3,1), (2,1) 등 구한 값을 다시 구해야 한다. 따라서 중복이 되는 경우는 메모이제이션을 통하여 중복을 제거 해주어야 한다. 코드 ( C++ ) #include #include using n..

  Read More