백준_동전1
https://www.acmicpc.net/problem/2293 [ 풀이 법 ] k원을 만드는 경우의 수는 아래의 그림과 같습니다. [ 그림 1. k원을 만드는 경우의 수 ] 우선, 위의 배열은 어떤 금액을 만드는 경우의 수입니다. 배열이름을 dp라고 하겠습니다. 그러면 dp(k)는 k원을 만드는 경우의 수입니다. 그리고 Cn은 n번째 동전의 가치입니다. 위의 예제 입력에서 C1은 1, C2는 2, C3은 5입니다. 그럼, 이런 식의 점화식이 가능합니다. dp( n, k ) = dp( n, k - Cn ) + dp( n - 1, k ) 이 점화식에서 dp( n, k )는 n개의 동전으로 k원을 만드는 경우의 수입니다. 그러므로 dp( n, k - Cn )은 n개의 동전으로 k - Cn을 만드는 경우의 ..
알고리즘/다이나믹 프로그래밍
2016. 7. 29. 13:04
KOI 초등 사과
https://www.acmicpc.net/problem/10833 [ 문제 풀이 ]사과를 사람 수로 나눈 나머지를 다 더하면 된다. [ 코드 ] 12345678910111213141516#include int main(void) { int n; int student, apple, remain = 0; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d %d", &student, &apple); remain += (apple % student); } printf("%d\n", remain); return 0;}
알고리즘/기초구현
2016. 7. 19. 10:42