고인물을 지양하는 블로그

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 기존 조합 문제에서 한 레벨 위의 문제라 할 수 있는데.. 크게 두 가지 부분에서 그렇다. 1) 일단 nCm 에서 n과m의 범위가 100으로 매우 크다. 2) long long을 쓰더라도 100C50의 결과값을 저장할 수 없다. 따라서 DP를 이용해 큰 수의 조합을 구하고, String을 이용해 결과값을 저장해 해결했다. string Add(string a, string b) { string ans; long long sum = 0; while(!a.empty() || !b.empty() || sum) { if(..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net $D_{i,j}$ 를 다음과 같이 정의하자. $D_{i,j} : C_{i}$ 원 까지 이용해 j원을 만드는 경우의 수 따라서 $C_{i}$ 원을 이용하는(할 수 있는) 경우, 이용하지 않는 경우 두 가지 경우로 나눌 수 있다. 각각의 경우는 이다. 따라서 점화식은 다음과 같다. 코드 1 #include #include #include int N,K; bool boun..