📙 Algorithm Solving/Java
📙[Algo] 24.07.02 알고리즘
혜덕hyeduck
2024. 7. 3. 03:27
알고리즘 문제) BOJ 17251. 힘 겨루기
문제 요약
- N명의 선수가 일렬로 있고, 1번부터 N-1까지 수가 적힌 공을 무작위로 뽑아 기준선으로 정하려함
- 예를 들어 3번 공을 뽑으면 3번과 4번 사이가 기준성
- 기준선 왼쪽은 R팀, 오른쪽은 B팀
- 예를 들어 3번 공을 뽑으면 3번과 4번 사이가 기준성
- 이때, 각 팀에서 가장 센 사람이 나오고 힘을 겨룬다.
- 이때 힘이 더 센 사람이 이긴다.
- 이길 확률이 높은 팀을 찾아라!
시간 제한
- 1초
입력
- 사람의 수 N이 주어진다.
- N은 1,000,000보다 작거나 같은 짝수
- 1번 사람부터 N번 사람까지의 힘을 나타내는 정수
- 각 사람의 힘은 10,000보다 작거나 같은 자연수
출력
- 이길 확률이 높은 팀을 출력 R 또는 B
- 만약 같다면 X 출력
접근법
- prefix배열과 suffix 배열을 만들었다.
- prefix 배열은 1번선수부터 N번선수까지 탐색하면서 더 센 선수를 만나면 해당 선수로 값을 저장
- suffix 배열은 N번선수부터 1번선수까지 탐색
- prefix 배열은 1번선수부터 N번선수까지 탐색하면서 더 센 선수를 만나면 해당 선수로 값을 저장
- 즉, prefix 배열을 통해 red팀이 이길확률, suffix배열을 통해 blue팀이 이길확률을 파악
- 우선 전체 선수중 가장 큰 선수의 힘은 prefix[N], suffix[0]에 저장될 것이다. → max값
- 이걸 기준으로 prefix와 suffix배열을 1번 인덱스부터 N번인덱스 까지 탐색하면서
- predix[i]가 max값과 같다면 red팀이 이길 확률로 카운트하고, → red
- suffix[i]가 max값과 같다면 blue팀이 이길 확률로 카운트했다. → blud
- 이때 둘의 값(red, blue)을 비교해서 누가 이길 확률이 높은지 판단
- 같다면 X 출력
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int[] prefix = new int[N + 1];
for (int i = 1; i <= N; i++) {
prefix[i] = Math.max(prefix[i - 1], arr[i]);
}
int[] suffix = new int[N + 2];
for (int i = N; i >= 0; i--) {
suffix[i] = Math.max(suffix[i + 1], arr[i]);
}
int red = 0, blue = 0;
for (int i = 1; i <= N; i++) {
if (prefix[i] == prefix[N]) red++;
if (suffix[i] == suffix[1]) blue++;
}
if (red == blue) System.out.println("X");
else if (red > blue) System.out.println("R");
else System.out.println("B");
}
}
알고리즘 문제) BOJ 11085. 군사 이동
문제 요약
- p개의 지점과 w개의 길이 존재
- 모든 길은 양방향이며, 각 길마다 너비가 존재
- 이때, 백준월드는 큐브월드로 가는 경로를 정해두고, 그 경로로만 군사를 보내려고 할 때,
- 경로 상 길 중 가장 좁은 길의 너비를 최대화하는 경로를 선택
- 이때, 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 출력
시간 제한
- 2초
입력
- p와 w
- 2 ≤ p ≤ 1 000, 1 ≤ w ≤ 50 000
- 백준의 수도 c와 큐브의 수도 v가 주어짐
- 0 ≤ c, v < p, c ≠ v
- w줄에 길이 연결하는 두 지점과 길의 너비가 공백을 사이에 두고 주어짐
출력
- 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 출력
접근법
- 크루스칼 알고리즘 사용
- 경로중 최소 너비가 가장 최대가 되게 구하는 것이므로,
- 일단, 너비 기준으로 그래프를 내림차순 정렬하고,
- 백준 나라와 큐브 나라가 이어질 때까지 트리를 구성
- 이때, 연결된 순간 그때 너비를 출력
- 너비가 큰 것부터 탐색하면서 트리를 구성헀기때문에,
- 백준과 큐브 사이에 경로가 형성된 순간 멈춰얄한다. (더 진행하면 가장 좁은 길의 너비를 최대화할 수 없으므로)
- 이때, 연결된 순간 그때 너비를 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int p, w, c, v;
static int[][] graph;
static int[] parent;
static int find(int x) {
if (parent[x] == x) return x;
parent[x] = find(parent[x]);
return parent[x];
}
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
parent[b] = a;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
p = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
c = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
graph = new int[w][3];
parent = new int[p];
for (int i = 0; i < p; i++) {
parent[i] = i;
}
int a, b, dist;
for (int i = 0; i < w; i++) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
dist = Integer.parseInt(st.nextToken());
graph[i][0] = a;
graph[i][1] = b;
graph[i][2] = dist;
}
Arrays.sort(graph, (o1, o2) -> {
return o2[2] - o1[2];
});
int ans = 0;
for (int i = 0; i < w; i++) {
a = graph[i][0];
b = graph[i][1];
dist = graph[i][2];
if (find(a) == find(b)) continue;
union(a, b);
ans = dist;
if (find(c) == find(v)) break;
}
System.out.println(ans);
}
}
알고리즘 문제) BOJ 17845. 수강 과목
문제 요약
- 최대 공부 시간 한계 안에서 괌고의 중요도 합이 최대가 되도록 수강하는 법을 찾아라
시간 제한
- 1초
입력
- 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)
- K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)
출력
- 얻을 수 있는 최대 중요도를 출력
접근법
- 재귀 dp로 구현했다.
- 현재 가리키는 수업과 지금까지의 공부시간을 기준으로 최대 만족도를 dp에 저장하도록 했다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, K;
static int[][] arr;
static int[][] dp = new int[1010][10010];
static int recur(int cur, int timeSum) {
if (timeSum > N) return Integer.MIN_VALUE;
if (cur == K) return 0;
if (dp[cur][timeSum] != -1) return dp[cur][timeSum];
int ret = 0;
ret = Math.max(ret, recur(cur + 1, timeSum + arr[cur][1]) + arr[cur][0]);
ret = Math.max(ret, recur(cur + 1, timeSum));
dp[cur][timeSum] = ret;
return ret;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[K][2];
int imp, time;
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
imp = Integer.parseInt(st.nextToken());
time = Integer.parseInt(st.nextToken());
arr[i][0] = imp;
arr[i][1] = time;
}
for (int[] d : dp) {
Arrays.fill(d, -1);
}
System.out.println(recur(0, 0));
}
}