10806. 수 만들기

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXTC4piqD_IDFASe 

SW Expert Academy

 

분류

우선순위 큐

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

거꾸로 계산하면 편하다.

X = 0에서 시작하지 말고 X = K에서 시작해서

나누기를 해가며 계산한다.

 

시행착오

없음

 

코드

import java.util.*;
import java.io.*;

class Solution{

	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int tc = 1; tc <= T; ++tc){
			int N = Integer.parseInt(br.readLine());
			int[] A = new int[N];
			String[] arr = br.readLine().split(" ");
			int K = Integer.parseInt(br.readLine());

			int min = Integer.MAX_VALUE;
			for (int i = 0; i < N; i++){
				A[i] = Integer.parseInt(arr[i]);
				min = Math.min(A[i], min);
			}

			Queue<Node> pq = new PriorityQueue<Node>();
			pq.add(new Node(K, 0));

			int cnt = K;

			while(!pq.isEmpty()){
				Node n = pq.poll();

				if (n.left == 0){
					cnt = n.cnt;
					break;
				}

				pq.add(new Node(0, n.cnt + n.left));

				for (int i = 0; i < N; i++){
					pq.add(new Node( n.left / A[i], n.cnt + n.left % A[i] ));
				}
			}

			System.out.println("#" + tc + " " + cnt);
		}
	}

	static class Node implements Comparable<Node>{
		int left, cnt;

		public Node(int left, int cnt){
			this.left = left;
			this.cnt = cnt;
		}

		public int compareTo(Node n){
			if (this.cnt > n.cnt) return 1;
			if (this.cnt == n.cnt) return 0;

			return -1;
		}
	}
}