📙[Algo] 24.07.02 알고리즘

알고리즘 문제) BOJ 17251. 힘 겨루기

• 링크 : https://www.acmicpc.net/problem/17251

문제 요약

• N명의 선수가 일렬로 있고, 1번부터 N-1까지 수가 적힌 공을 무작위로 뽑아 기준선으로 정하려함
  • 예를 들어 3번 공을 뽑으면 3번과 4번 사이가 기준성
    • 기준선 왼쪽은 R팀, 오른쪽은 B팀
• 이때, 각 팀에서 가장 센 사람이 나오고 힘을 겨룬다.
  • 이때 힘이 더 센 사람이 이긴다.
• 이길 확률이 높은 팀을 찾아라!

시간 제한

• 1초

입력

• 사람의 수 N이 주어진다.
  • N은 1,000,000보다 작거나 같은 짝수
• 1번 사람부터 N번 사람까지의 힘을 나타내는 정수
  • 각 사람의 힘은 10,000보다 작거나 같은 자연수

출력

• 이길 확률이 높은 팀을 출력 R 또는 B
• 만약 같다면 X 출력

접근법

• prefix배열과 suffix 배열을 만들었다.
  • prefix 배열은 1번선수부터 N번선수까지 탐색하면서 더 센 선수를 만나면 해당 선수로 값을 저장
    • suffix 배열은 N번선수부터 1번선수까지 탐색
• 즉, 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. 군사 이동

• 링크 : https://www.acmicpc.net/problem/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. 수강 과목

• 링크 : https://www.acmicpc.net/problem/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));

    }
}