문제 1)
입력)
첫째 줄에 n,m 이 주어진다.
이후의 n개의 줄에는 각 화폐의 가치가 주어진다.
출력)
첫째 줄에 최소 화폐 개수를 출력한다.
불가능 할때는 -1 출력한다.
입력 예시1)
2 15
2
3
출력 예시1)
5
입력 예시2)
3 4
3
5
7
출력 예시2)
-1
시간 제한: 1초 / 메모리 제한: 128MB
문제 풀이)
이중 for문을 사용하여 화폐의 개수 n 만큼 반복하여(각 화폐로 구할수있는 금액 확인) d의 값의 저장하여 구할수 있는지 없는지 확인하면 된다.
문제 2)
입력)
출력)
테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력 합니다. 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다.
입력 예시)
출력 예시)
19
16
시간 제한: 1초 / 메모리 제한: 128MB
문제 풀이)
문제 3)
입력)
출력)
첫째 줄에 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력합니다.
입력 예시)
7
15 11 4 8 5 2 4
출력 예시)
2
시간제한: 1초 / 메모리 제한: 256MB
문제 풀이)
가장 긴 증가하는 부분 수열(LIS)을 응용하여 본문제의 가장 긴 감소하는 부분수열을 찾으면 된다.
:)