목록2017/05/19 (2)
개인공부용123 프로그래밍 블로그
[백준] 6591
어렵게 생각하지않고 손으로 계산하듯이 풀면 풀립니다 이때 nCr = nCn-r 이 될수있음을 이용해서 n-r > n >> k; if (n == 0 && k == 0) break; if (n - k < k) k = n - k; ll Answer = 1; for (ll i = 1; i
알고리즘문제
2017. 5. 19. 21:17
[백준] 11051 이항계수문제
해당문제는 이항계수문제로 n과 k가주어졌을경우 nCk % 10007을 한 결과를 구하는 문제입니다. nCk = n-1Ck-1 + n-1Ck로 나타낼수있습니다. 이를 DP를 이용해서 풀면 cache[1001][1001] 배열에 nCk의 값을 저장해두고 해당 값이 필요할경우 배열에 있는 값을 이용하면 문제를 더욱빠르게 풀수있습니다. #include #include using namespace std; //이항계수 // 점화식 nCk = n-1Ck-1 + n-1Ck typedef long long ll; const ll divideNum = 10007; ll cache[1001][1001]; ll Answer(int N, int K) { if (N == K || K == 0) return 1; ll& ret ..
알고리즘문제
2017. 5. 19. 19:45