시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 64 MB | 489 | 136 | 116 | 44.106% |
동전 교환 문제는 흔히 동적계획법의 기초 문제로 많이 소개된다. 동전 교환 문제는 아래와 같다.
병찬이는 이 문제를 다소 단순한 방법으로 풀려고 한다. 병찬이가 이 문제를 해결하는 방법은 아래와 같다.
하지만, 병찬이의 방법은 특정 상황에서 최적이 아닐 수 있다. 만약 8원을 액면이 1, 4, 6인 동전으로 바꾼다면, 병찬이의 방법으로는 6원짜리 1개, 1원짜리 2개로 총 3개의 동전으로 바꾼다. 하지만 실제로는 4원짜리 2개로 바꾸는 것이 더 좋다.
병찬이는 자신이 방법이 특정 액면에서는 통하지만 그렇지 않은 경우도 있다는 것을 깨달았다. 병찬이를 도와 동전의 액면이 주어질 때, 병찬이의 방법이 모든 C에 대해서 통하는지 구하는 프로그램을 작성하여라.
첫 번째 줄에는 동전 단위의 수 N이 주어진다. (1 ≤ N ≤ 100)
두 번째 줄에는 동전의 단위 액면 값 P1, P2, …, PN이 주어진다. 단, 1 = P1 < P2 < … < PN ≤ 100,000을 만족한다.
만약 병찬이가 사용한 방법이 항상 최적이라면 'Yes'를 출력하고, 그렇지 않다면 'No'를 출력한다.
8 1 5 10 50 100 500 1000 10000
Yes
3 1 4 6
No
Contest > BOJ User Contest > FunctionCup > FunctionCup 2016 E번