99클럽 코테 스터디 21일차 TIL

비기너

문제

19638번: 센티와 마법의 뿅망치

# 우선순위 큐

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

풀이

t번 이내에 마법의 뿅망치를 사용해서 센티보다 키가 큰 거인이 없도록 할 수 있는지를 구하는 문제이다.

뿅망치의 사용 횟수가 정해져 있으므로 키가 가장 큰 거인부터 뿅망치를 적용해야 한다.

따라서 우선순위 큐를 이용해서 맥스 힙을 구현하여 가장 키가 큰 거인을 찾을 수 있도록 한다.

뿅망치를 이용하다가 우선순위 큐의 top 요소가 1이거나 센티의 키보다 작으면 반복문을 탈출한다.

그 뒤 우선순위 큐의 top 요소와 센티의 키를 비교해서 결과를 출력한다. 

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < n; i++)
			pq.add(Integer.parseInt(br.readLine()));

		int i;
		for (i = 0; i < t; i++) {
			if (pq.peek() < h || pq.peek() == 1)
				break;
			else
				pq.add(pq.poll() / 2);
		}

		if (pq.peek() >= h)
			bw.write("NO\n" + pq.peek());
		else
			bw.write("YES\n" + i);
		bw.flush();
		bw.close();
	}
}

미들러

문제

카펫

# 완전탐색

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

풀이

카펫의 노란 영역과 갈색 영역의 크기가 주어졌을 때 카펫의 가로와 세로를 구하는 문제이다.

가운데 노란 영역이 직사각형이기 때문에 노란 영역의 가로, 세로가 될 수 있는 모든 정수 쌍을 구해서 갈색 영역의 크기가 되는지 확인해 보면 된다.

코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] ans = new int[2];
        
        for (int i = 1; i <= (int)Math.sqrt(yellow); i++) {
            if (yellow % i != 0)
                continue;
            int y = i;
            int x = yellow / i;
            if (2 * x + 2 * y + 4 == brown) {
                ans[0] = x + 2;
                ans[1] = y + 2;
                return ans;
            }
                
        }
        
        return ans;
    }
}

챌린저

문제

17182번: 우주 탐사선

# 플로이드-워셜 # 완전탐색

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

풀이

우주 탐사선이 행성 k에서 출발할 때 모든 행성을 탐사하는데 걸리는 최소 시간을 구하는 문제이다.

플로이드 워셜 알고리즘을 이용해서 모든 행성들 간의 최소 시간을 구한다.

행성 k에서 출발해서 모든 행성을 탐사하는 모든 경로를 살펴봐 그 중 시간이 최소인 것을 출력한다.

코드

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

public class Main {
	static int d[][];
	static boolean[] visited;
	static int n, ans = 1000000000;

	static void go(int x, int cnt, int sum) {
		if (cnt == n - 1) {
			ans = Math.min(ans, sum);
			return;
		}

		for (int i = 0; i < n; i++) {
			if (visited[i])
				continue;
			visited[i] = true;
			go(i, cnt + 1, sum + d[x][i]);
			visited[i] = false;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		d = new int[n][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++)
				d[i][j] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++)
					d[j][k] = Math.min(d[j][k], d[j][i] + d[i][k]);
			}
		}

		visited = new boolean[n];
		visited[m] = true;
		go(m, 0, 0);

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}