[BaekJoon]백준 11047번_동전0 for JAVA

 

 

 

 

 

 

 

---

 

동전0

 

이 문제는 그리디 알고리즘 유형에 있는 문제이다.

 

 

 

https://ticssfm.tistory.com/32?category=1008893 

[Algorithm] 탐욕(그리디) 알고리즘 (greedy algorithm)

 

 

필요한 동전의 개수라는 말만 봐도 그리디를 사용함을 알 수 있다.

 

 

 

그리디는 가장 최적의 값을 우선적으로 할당해주는 알고리즘이므로 본 문제를 풀 때 가장 큰 값을 먼저 대입해봐야한다.

 

 

Ai는 Ai-1의 배수라는 말은.. 어차피 입력은 여기서 해줄 것이기 때문에 신경쓰지 않을 것이다...(굳이 넣으려면 넣을순 있음)

 

 

 

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Baek11047 {
	public static void  main(String[] args) throws IOException{ // 동전0
		//동전종류 N, 합 K 띄어쓰기로 입력받고 줄바꿔서 N개의 동전의 가치가 오름차순으로 주어짐 + N >= 2이면 배수로;;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken()); // 동전 종류 개수
		int K = Integer.parseInt(st.nextToken()); // 합
				
		int coin[] = new int[N];
		
		for(int i = 0; i < N; i++) { // 동전의 종류 입력받음
			coin[i] = Integer.parseInt(br.readLine());
		}
		
		int last = K;
		int count = 0;
		
		for(int i = N-1; i >=0; i--) {
			//if(last % coin[i] != last) {  
				count += last / coin[i];   // 어차피 더 큰값이면 몫이 0이기때문에 그냥 더해주면 됨!
				last = K - coin[i] * (K/coin[i]);
				if(last == 0) break;
			//} else {continue;}
		}
		
		System.out.println(count);
		
	}

}

 

 

 

가장 큰 값부터 대입하기 위해 오름차순으로 대입된 배열을 거꾸로 count 해준다.

 

 

 

 

 

 

 

 

 

 

위에가 주석으로 지운 if문을 넣었을 때, 아래가 뺐을 때이다.

 

 

 

남의 코드를 살펴보니 확실히 배열을 사용하는 것보다 arraylist를 사용하는 것이 훨!!씬 효율적이었다.