글 읽기 - 동전 0 질문입니다. 틀렸다고 나옵

iolk1001 6년 전 0

탐욕적으로 풀었다고 생각햇는데 반례가 어떤게 있을까요..?

import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		int[] arr = new int[n+1];
		int idx = -1;
		int cnt = 0;
		
		for(int i=0; i<n; i++){
			arr[i] = sc.nextInt();
			if(arr[i] <= k ) idx = i;
		}
		for(int i = idx; i >= 0; i--){
			if(arr[i] <= k){
				int m = k / arr[i];
				k -= m * arr[i];
				cnt += m;
			}
			if( k == 0 ) break;
		}
		
		System.out.println(cnt);
		
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

동전 0 질문입니다. 틀렸다고 나옵

iolk1001 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말