문제 13. 발전기 (2)
바로 앞에서 푼 발전기 문제와 비슷하다고 생각할 수도 있지만, 다르다.
건물 유형 번호를 출력하는 것이기 때문에, count 배열로 건물 유형에 따른 건물 개수를 저장하고 비교를 통해 해당 index를 출력한다.
보통 BFS는 visited 배열을 따로 두어 방문 표시를 하는데, 이 문제에서는 map 배열에 값을 저장해서 새롭게 배열을 생성하지 않고 방문 표시를 한다는 점이 신선했다.
import java.io.*;
import java.util.*;
class Main {
static int N, K;
static int map[][];
static int result = Integer.MIN_VALUE;
static int count[];
static Queue<int[]> queue;
static int dy[] = {1, 0, -1, 0};
static int dx[] = {0, 1, 0, -1};
static int result_index;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str[] = br.readLine().split(" ");
N = Integer.parseInt(str[0]);
K = Integer.parseInt(str[1]);
count = new int[31];
queue = new LinkedList();
map = new int[N][N];
result_index = 0;
for(int i = 0; i < N; i++) {
str = br.readLine().split(" ");
for(int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(str[j]);
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(map[i][j] != 31 && map[i][j] != 0) {
int n_num = map[i][j];
queue.add(new int[]{i, j});
map[i][j] = 31;
int k_count = 0;
while(!queue.isEmpty()) {
int now[] = queue.poll();
int y = now[0];
int x = now[1];
k_count++;
for(int k = 0; k < 4; k++) {
int n_y = y + dy[k];
int n_x = x + dx[k];
if(n_y < 0 || n_y >= N || n_x < 0 || n_x >= N) {
continue;
}
if(map[n_y][n_x] == n_num) {
queue.add(new int[]{n_y, n_x});
map[n_y][n_x] = 31;
}
}
}
if(k_count >= K) {
count[n_num] += 1;
}
}
}
}
for(int i = 1; i < 31; i++) {
if(count[i] >= result) {
result = count[i];
result_index = i;
}
}
System.out.println(result_index);
}
}
문제 14. 작은 노드
방문할 수 있으면서, 번호가 가장 작은 노드로 이동한다라는 부분을 놓치면 안된다.
이 부분은 해당 지점에서 방문할 수 있는 지점을 찾을 때, 1번부터 N번까지 연결되었는지 확인하고 방문 안된 지점이 있으면 바로 queue에 넣은 후에 break로 반복문을 탈출하는 방식으로 구현할 수 있었다.
import java.io.*;
import java.util.*;
class Main {
static int N, M, K;
static int count = 0;
static boolean map[][];
static boolean visited[];
static Queue<Integer> queue;
static int now;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str[] = br.readLine().split(" ");
N = Integer.parseInt(str[0]);
M = Integer.parseInt(str[1]);
K = Integer.parseInt(str[2]);
map = new boolean[N+1][N+1];
visited = new boolean[N+1];
for(int i = 0; i < M; i++) {
str = br.readLine().split(" ");
map[Integer.parseInt(str[0])][Integer.parseInt(str[1])] = true;
map[Integer.parseInt(str[1])][Integer.parseInt(str[0])] = true;
}
queue = new LinkedList();
queue.add(K);
visited[K] = true;
while(!queue.isEmpty()) {
now = queue.poll();
count++;
for(int i = 1; i <= N; i++) {
if(map[now][i] && !visited[i]) {
queue.add(i);
visited[i] = true;
break;
}
}
}
System.out.println(count + " " + now);
}
}
문제 15. 과일 구매
그리디 문제이다.
- 최대 포만감을 얻기 위해 포만감이 큰 과일부터 구매한다.
- 조각 당 포만감 수치가 가장 높은 과일부터 구매하되, 현재 가진 돈이 부족해서 과일을 온전히 구매할 수 없는 상황에만 조각 단위로 과일을 구매한다.
따라서 정렬 조건은 다음과 같다.
1. 가격당 포만감 수치로 비교하여 구매한다.
2. 가격이 더 저렴한 것을 구매한다.
import java.io.*;
import java.util.*;
class Main {
static int N, K;
static int[] P, C;
static long ans;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str[] = br.readLine().split(" ");
N = Integer.parseInt(str[0]);
K = Integer.parseInt(str[1]);
ans = 0;
P = new int[N];
C = new int[N];
for(int i = 0; i < N; i++) {
str = br.readLine().split(" ");
P[i] = Integer.parseInt(str[0]);
C[i] = Integer.parseInt(str[1]);
}
List<double[]> cost = new ArrayList<>();
for(int i = 0; i < N; i++) {
cost.add(new double[]{(double)C[i]/P[i], (double) P[i]});
}
// 가격당 포만감 수치가 같다면, 가격으로 비교(가격이 더 저렴한 것을 구매!)
Collections.sort(cost, (a, b) -> Double.compare(b[0], a[0]) != 0 ?
Double.compare(b[0], a[0]) :
Double.compare(b[1], a[1]));
for(int i = 0; i < N; i++) {
double[] pair = cost.get(i);
double value = pair[0];
double amount = pair[1];
double buy = Math.min(amount, K);
K -= buy;
ans += value * buy;
}
System.out.println(ans);
}
}
이번주는 이사 준비로 기한 내에 못 풀어서 바지가 누락되었다.. 미안 블럭아!😩
반응형
