글 읽기 - 그리디알고리즘을 사용한건지 궁금합니다 자바

jwl2327 4년 전 0

문제는 간단한데 목적은 그리디 알고리즘을 사용하는 거자나요?

제가 푸는거는 아래처럼 풀어서 정답으로 나왔는데

알고리즘을 제대로 이해하고 푼게 아니라 그리디가 절대 아닐건데...

혹시 대충 그리디알고리즘으로 풀려고 할려면 필요한 방향정도만 알려주실수있나요?

import java.util.Scanner;

/*
 * 
 * https://www.acmicpc.net/problem/11047
 * 동전0
 * 
 * 10 4200
1
5
10
50
100
500
1000
5000
10000
50000
 */
 class Main {
	static int N, K, sum;
	static int[] money;
	static int coin=0, number=0;
	
	public static void main(String[] args) {      
		Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        money = new int[N];
        for (int i=0;i<N;i++) {
        	money[i]=sc.nextInt();
        }
        sc.close();
        for (int i=N-1;-1<i;i--) {
        	coin = money[i];
        	while (sum+coin<=K) {
        		sum += coin;
        		number++;
        		//System.out.println(sum+" "+coin+" "+ number);
        	}
        }
        System.out.println(number);
	}
}

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

문제

문제

출처

ICPC

그리디알고리즘을 사용한건지 궁금합니다 자바

jwl2327 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말