13137번 - Exchange Problem

문제

동전 교환 문제는 흔히 동적계획법의 기초 문제로 많이 소개된다. 동전 교환 문제는 아래와 같다.

• 거스름돈 C원을 액면이 P₁, P₂, …, P_N인 동전으로 바꿀 때, 최소 몇 개의 동전이 필요한가?

병찬이는 이 문제를 다소 단순한 방법으로 풀려고 한다. 병찬이가 이 문제를 해결하는 방법은 아래와 같다.

• 매 순간마다, 더 필요한 돈 이하의 액면을 가진 동전 중 가장 액면이 높은 동전을 추가한다. 이 방식으로 C원을 모두 채울 때까지 반복한다.

하지만, 병찬이의 방법은 특정 상황에서 최적이 아닐 수 있다. 만약 8원을 액면이 1, 4, 6인 동전으로 바꾼다면, 병찬이의 방법으로는 6원짜리 1개, 1원짜리 2개로 총 3개의 동전으로 바꾼다. 하지만 실제로는 4원짜리 2개로 바꾸는 것이 더 좋다.

병찬이는 자신이 방법이 특정 액면에서는 통하지만 그렇지 않은 경우도 있다는 것을 깨달았다. 병찬이를 도와 동전의 액면이 주어질 때, 병찬이의 방법이 모든 C에 대해서 통하는지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 동전 단위의 수 N이 주어진다. (1 ≤ N ≤ 100)

두 번째 줄에는 동전의 단위 액면 값 P₁, P₂, …, P_N이 주어진다. 단, 1 = P₁ < P₂ < … < P_N ≤ 100,000을 만족한다.

출력

만약 병찬이가 사용한 방법이 항상 최적이라면 'Yes'를 출력하고, 그렇지 않다면 'No'를 출력한다.

제한

힌트