[Java/백준(boj)] 11047번. 동전 0

[Greedy Algorithm]

Baekjoon Online Judge

 11047번. 동전 0 

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

―　Algorithm Note　―

- 동전의 가치가 오름차순으로 주어짐
- 그러므로 따로 동전 값들을 정렬하거나 그럴 필요 없이 배열에 저장 후 index가 큰 것부터 사용가능한 동전인지 판별

- 사용가능한 동전일 경우, 최종 가치의 합인 K에서 빼줌으로써 K가 0인 경우 결과값을 return하는 방식으로 코드 작성
- 처음엔 사용가능한 동전이 나왔을 경우 K가 0보다 작거나 같아질때까지 K에서 동전의 가치를 빼주는 방법으로 코드를 작성하였으나, 시간복잡도가 n^2이 나와 시간복잡도를 줄일 수 있는 방법으로 다시 생각함.

- 마이너스가 아닌 나누기를 사용해 시간복잡도를 줄임.
- 나누기를 사용해 코드를 작성하면, 몫이 0이 아닌 경우 현재 판별하는 동전이 사용가능하다고 판단.
- 사용가능한 동전일경우 몫을 필요한 동전 개수의 최소값을 저장하는 변수에 더하는 방식.
- 이 방식을 사용할경우 시간복잡도 O(n)

 

Source Code (변경 전)

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

public class Main {
  public static int solution(int n, int k, int[] coin) {
      int cnt = 0; // 동전 개수
      for(int i = n - 1; i >= 0; i--) {
          if(k == 0) {
              return cnt;
          }

          while(true) {
              k -= coin[i];
              if(k < 0) {
                  // 만약 잘못된 동전이라면 (현재 금액보다 동전의 가치가 더 클 때)
                  k += coin[i];
                  System.out.println("if");
                  break;
              }
              cnt++; // 여기까지 코드가 넘어온다면 현재 금액에서 가장 큰 가치의 동전을 선택한 것
              System.out.println("k : " + k + ", cnt : " + cnt);
          }
      }
      return cnt;
  }

  public static void main(String[] args) throws NumberFormatException, IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = null;

      st = new StringTokenizer(br.readLine(), " "); // NumberFormatException, IOException 처리
      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());
      }
      System.out.println(solution(n, k, coin));
  }
}

 

 

 

Source Code ( 변경 후)

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

public class Main {
	public static int solution(int n, int k, int[] coin) {
		int cnt = 0; // 동전 개수
		for(int i = n - 1; i >= 0; i--) {
			if(k == 0) {
				return cnt;
			}
			
			int tmp = 0; // 남은 값을 동전으로 나눈 몫을 임시로 저장하는 변수
			tmp = k / coin[i];
			if(tmp > 0) {
				// 만약 몫이 0보다 크면 해당하는 동전으로 가치를 환산할 수 있으므로
				k -= coin[i] * tmp; // 총액에서 해당하는 동전 * 환산 가능 개수를 빼고
				cnt += tmp; // 동전의 개수에 몫을 더한다.
			}
			System.out.println("k : " + k + ", cnt : " + cnt);
		}
		return cnt;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine(), " "); // NumberFormatException, IOException 처리
		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());
		}
		System.out.println(solution(n, k, coin));
	}
}

 

 

Result ( 실행 결과 및 채점 결과 )

 

백준 예제 2번으로 실행한 결과입니다

 

 

 

112ms : 마이너스로 푼 것 (변경 전)

84ms : 나누기로 푼 것 (변경 후)

 

 

 

 

오류나 궁금하신게 있으시면 언제든 댓글 달아 주시고,

코드 참조하실땐 공감 한번 눌러주시면 저에게 큰 힘이 됩니다 :)