📙[Algo] 24.08.03 알고리즘

알고리즘 문제) BOJ 31589. 포도주 시음

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

문제 요약

• N종류의 포도주가 존재하며, 각각 맛을 지니고 있다
• 이때, 첫 잔을 마실 때는 포도주 본연의 맛을 느끼지만
  • 그 이후부터 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 0의 맛을 느끼며
  • 맛없는 포도주를 마시다가 맛있는 포도주를 마시면 두 포도주의 맛의 차이만큼 느낀다
• 이때 K종류의 포도주만 마신다 했을 때, 최대로 느낄 수 있는 맛을 구해라

시간 제한

• 1초

입력

• 포도주의 수 N, 마셔야할 포도주 수 K
  • 1 ≤ K ≤ N ≤ 30만
• N개의 포도주 맛 Ti가 주어진다
  • 1 ≤ Ti ≤ 10억

출력

• 맛의 합의 최댓값은?

접근법

• 순차적으로 먹게 될 경우 맛의 차이만큼 먹게된다.
• 이때, 순차적으로 먹게 될 경우 결국 간격의 합(맛의 차이) 만큼 누적해서 마시게 되므로, 마지막으로 먹게되는 포도주 맛만큼 맛을 보게 된다.
• 그렇기 때문에 무조건 순차적으로 먹는게 최선의 답이 될 수 없다는 결론이 생긴다
• 따라서 먼저 가장 맛있는 포도주 → 남아있는 포도주 중 가장 맛없는 포도주 → 남아있는 포도주 중 가장 맛있는 포도주 이렇게 번갈아 마셔야 한다.
  • 이 때 더 맛없는 포도주를 마시게 될경우 맛은 안느끼게 되므로
    • 가장 맛있는 포도주 + (남아있는 포도주 중 가장 맛있는 포도주 - 남아있는 포도주 중 가장 맛없는 포도주) + (남아있는 포도주 중 가장 맛있는 포도주 - 남아있는 포도주 중 가장 맛없는 포도주) + …
    • 이런식으로 더해지게 된다.
• 따라서 K가 2이 이하일 경우에는 가장 맛있는 포도주 맛이 정답이 되며,
• 그 이상일 경우 투 포인터를 사용하여
  • 맛의 차이만큼 누적해서 더해주도록 했다 ⇒ arr[e] - arr[s]
• 이때 정답에는 가장 맛있는 포도주를 미리 마셨다고 생각하고 투포인터를 진행했기때문에
  • ans = arr[N-1]
  • s = 0, e = N-2
  • remain = K - 1 ⇒ 마셔야 할 포도주 개수
  • 로 초기화해서 진행했다
• 여기서 주의할 점은 remain값이 1일 경우가 아닌 경우에만 (가장 맛난 포도주, 가장 맛없는 포도주)쌍으로 마시게 했다.
  • 한 잔이 남은 경우에는 가장 맛없는 포도주만 마시므로 0의 맛만 느낀다.

코드

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;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        if (K <= 2) System.out.println(arr[N - 1]);
        else {
            // 3 5 5 5 6 7 8 9 15
            // 15 3 9 5 8 = 15  + 6 + 3 = 24
            // 15 3 9 5 8 5 = 15 6 3 = 24
            // 15 3 9 5 8 5 7 = 15 6 3 2 = 26

            int s = 0, e = N - 2, remain = K - 1;
            long ans = arr[N - 1];
            while (0 < remain) {
                if (remain != 1) ans += arr[e] - arr[s];
                s++;
                e--;
                remain -= 2;
            }
            System.out.println(ans);
        }

    }
}

 

알고리즘 문제) BOJ 13424. 비밀 모임

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

문제 요약

• 1~N번의 방이 존재
• N개의 방은 M개의 통로로 연결되어 있으며 양방향 통행 및 자연수의 길이를 가짐
• 모임에 K명의 친구들이 참여할 때,
• 이동거리가 최소가 되도록 하는 모임 장소를 찾아 출력해라

시간 제한

• 1초

입력

• T개의 테스트 케이스
• 각 테스트 케이스별로
  • 첫째 줄에는 방의 개수 N, 비밀 통로 개수 M
    • 2 ≤ N ≤ 100
    • N-1 ≤ M ≤ N*(N-1)/2
  • M개의 줄에 걸쳐 비밀통로 정보 a b c
    • a번 방과 b번 방은 길이 c의 통로로 연결
      • c는 1~1000이하 자연수
    • 두 방을 연결하는 통로는 하나씩만 존재
    • 또한 어떤 방에서 다른방으로 통로를 통해 모두 이동 가능
  • 친구의 수 K
    • 1 ≤ K ≤ N
  • 현재 친구들이 위치해있는 방 번호 K개가 공백을 두고 주어짐

출력

• 1줄에 테스트케이스별로 이동 거리가 최소가 되는 모임 장소의 방 번호를 출력

코드

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

public class Main {
    static final int INF = 1_000_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N, M;
        int[][] arr;
        int a, b, c, f, idx, sum, min, ans;
        int[] friend;
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 방의 수
            M = Integer.parseInt(st.nextToken()); // 비밅통로 개수

            arr = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (i != j) arr[i][j] = INF;
                }
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                a = Integer.parseInt(st.nextToken()) - 1;
                b = Integer.parseInt(st.nextToken()) - 1;
                c = Integer.parseInt(st.nextToken());

                arr[a][b] = Math.min(arr[a][b], c);
                arr[b][a] = Math.min(arr[b][a], c);
            }

            f = Integer.parseInt(br.readLine());
            friend = new int[f];
            idx = 0;
            st = new StringTokenizer(br.readLine());
            while (idx < f) {
                friend[idx++] = Integer.parseInt(st.nextToken()) - 1;
            }

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

            min = 1 << 30;
            ans = 0;
            for (int i = 0; i < N; i++) {
                sum = 0;
                for (int j = 0; j < f; j++) {
                    sum += arr[i][friend[j]];
                }

                if (min > sum) {
                    min = sum;
                    ans = i;
                }
            }

            sb.append(ans + 1).append("\n");
        }

        System.out.println(sb);
    }
}

 

알고리즘 문제) BOJ 2617. 구슬 찾기

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

문제 요약

• N개의 구슬이 존재
  • N은 무조건 홀수이며, 구슬은 1번 ~ N번 존재
• 이때, M개의 쌍의 구슬에 대해 어느 쪽이 더 무거운 지에 대한 정보를 알고 있다
• 이때 무게가 절대 전체 구슬의 중간일 수 없는 구슬의 개수를 찾아라
  • 중간 = (N + 1)/2

시간 제한

• 1초

입력

• 구슬 개수 N, 저울에 올려 본 쌍의 개수 M
  • 1 ≤ N ≤ 99
  • 1 ≤ M ≤ N*(N-1)/2
• M개의 줄에 두 개의 구슬 번호가 주어짐
  • a b
    • a가 b보다 더 무겁다

출력

• 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력

코드

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

public class Main {
    static int N, M;
    static int[][] arr;
    static final int INF = 1_000_000_000;

    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());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i != j) arr[i][j] = INF;
            }
        }

        int a, b;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken()) - 1;
            b = Integer.parseInt(st.nextToken()) - 1;

            // a가 b보다 무겁다
            arr[a][b] = 1;
        }

        // 플로이드워셜
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
                }
            }
        }

        int more, less, ans = 0;
        for (int i = 0; i < N; i++) {
            more = 0;
            less = 0;
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == INF && arr[j][i] != INF) less++;
                else if (arr[i][j] != INF && arr[j][i] == INF) more++;
            }

            if (more > N / 2 || less > N / 2) ans++;
        }

        System.out.println(ans);
    }
}