[SW Expert Academy, SWEA 10806] 수 만들기 (java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXTC4piqD_IDFASe&categoryId=AXTC4piqD_IDFASe&categoryType=CODE&problemTitle=%EC%88%98+%EB%A7%8C%EB%93%A4%EA%B8%B0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

728x90

---

메모리: 36,356 KB, 시간: 239 ms

사용 알고리즘: 우선순위 큐

 

내 생각

도저히 감이 안와서 다른 블로그 풀이 참고했다.

여기서 아이디어를 얻었고, 여기 코드를 참고했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Solution  {
 
    public static void main(String[] args) throws Exception{
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        // T := 테스트 케이스의 수
        int T = Integer.parseInt(br.readLine());
 
        int N, K, result; int[] arr, now;
        for (int tc = 1; tc <= T; tc++) {
            // N := 정수 개수
            N = Integer.parseInt(br.readLine());
 
            // 정수 입력
            arr = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
 
            // K := 만들고자 하는 수
            K = Integer.parseInt(br.readLine());
 
            // K에서 0을 만들어주는 경우 확인 (1을 뺀 횟수로 올림차순 정렬)
            PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
            pq.add(new int[] {K, 0});
 
            while(!pq.isEmpty()) {
                now = pq.poll();
 
                if(now[0] == 0) { // 0 만든 경우 확인
                    System.out.println("#" + tc + " " + now[1]);
                    break;
                }
 
                // 1 빼기로 0 만든 경우 pq에 넣기
                pq.add(new int[] {0, now[1] + now[0]});
 
                // 1 빼기로 arr[i]로 나누어 떨어지게 만든 후, arr[i]로 나눈 경우
                for (int i = 0; i < N; i++) {
                    pq.add(new int[] {now[0] / arr[i], now[1] + now[0] % arr[i]});
                }
            }
        }
    }
 
}