백준 #11047 java 2023.01.31

동전 0 문제! 3-1학기에 컴퓨터 알고리즘이라는 수업을 듣게 되는데, 거기에 그리디 알고리즘이라고 것을 배운다고 나와있어 그리디 알고리즘과 관련된 문제를 풀어보았다.

 

나눌 수 있는 값 중 가장 큰 값으로 나눠야 하는 것을 생각해야 하는 문제!

 

package boj_basic.stepp10;

import java.util.Scanner;

public class Q11047 {

	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 num = 0;
		
		for(int i = 1; i<=N; i++) {
			int A = sc.nextInt();
			arr[i]=A;
		}
		
		int sum = 0;
		
		while(K!=0) {
			for(int i = 1; i<=N; i++) {
				if(arr[i]<=K) {
					num = arr[i];
				}
					
			}
			sum += K/num;
			K = K%num;
		}
		System.out.println(sum);

	}

}

배열에다 A값들을 다 집어넣고 

for문으로 배열에 처음부터 끝까지 돌면서 나눌 수 있는 수 중 가장 큰 수가 num이 될 수 있게 코드를 구현하였다.

그 다음에 K/num을 한 몫의 값을 sum에다가 계속 더해주고, 나머지 값은 다시 K로 재설정해주어 K=0이 될 때 반복문을 나올 수 있도록 하였다!

 

마지막에 sum을 출력해주면 끝!