📙[Algo] 24.03.27 알고리즘

알고리즘 문제) BOJ 19590. 비드맨

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

문제 요약

• 서로 다른 두 종류의 구슬 두 개를 부딪히면 서로 깨져 없어짐
• 이 사실을 이용해 현재 가지고 있는 구슬 개수를 최소화 하고자 함
• 서로 다른 종류의 구슬 두 개를 부딪혀서 최대한 구슬을 없앤다고 할 때 남게 되는 구슬의 개수는 몇 개인지를 구하기

시간 제한

• 1초

입력

• 비드맨이 가지고 있는 구슬 종류 N
  • 1≤N≤10^5
• N개의 줄에 x1, x2, … , xN이 주어짐
  • xi : 비드맨이 가지오 있는 i번째 종류의 구슬 개수
    • 1≤xi≤1억

출력

• 최대한 많이 구슬을 없앴을 때 남은 구슬 개수?

접근법

• if 가장 큰 값을 제외한 나머지 친구들의 총 합 < 가장 큰 값
  • 가장 큰 값 - 나머지 합
• if 나머지 합 == 가장 큰 값 → 0
• if 나머지 합 > 가장 큰 값
  • 홀수 홀수 ⇒ 0
  • 짝수 짝수 ⇒ 0
  • 홀수 짝수 / 짝수 홀수 ⇒ 1
• 연산1 : 나머지에서 하나, 가장 큰 거 하나 빼기 ⇒ 나머지 하나 감소, 가장 큰 값 하나 감소
• 연산2 : 나머지에서 둘 빼기 ⇒ 나머지 합이 2 감소

코드

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

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));

        int N = Integer.parseInt(br.readLine());

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

        Arrays.sort(arr);
        long sum = 0;
        for (int i = 0; i < N - 1; i++) {
            sum += arr[i];
        }

        if (sum <= arr[N - 1]) bw.write(String.valueOf(arr[N - 1] - sum));
        else bw.write(String.valueOf((arr[N - 1] + sum) % 2));

        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2138. 전구와 스위치

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

문제 요약

• N개의 스위치와 N개의 전구
• 만약 i번 스위치를 누르면 i-1,i,i+1 세 개의 전구 상태가 바뀜
• N개의 전구들의 현재 상태와 만들고자 하는 상태가 주어졌을 때
  • 그 상태를 만들기 위해 최소 몇 번 눌러야 할까?

시간 제한

• 2초

입력

• 자연수 N
  • 2≤N≤10만
• 전구의 현재 상태를 나타내는 숫자 N
• 만들고자 하는 상태를 나타내는 숫자 N
  • 0 : 켜져있음, 1: 꺼져있음

출력

• 최소 몇 번 눌러야 하는 지 출력
  • 없다면 -1

접근법

000

110

101

010

• 같은 스위치를 두번 이상 누르는건 의미 X
• i번째 전구를 누를지 말지 결정 ⇒ i-1번째 전구 상태가 목표로하는 전구와 같다면 누르면 안 되고, 다르다면 누른다.

코드

import java.io.*;

public class Main {
    static int N;
    static String before;
    static String after;
    static char[] current;
    static int answer = 1 << 30;

    static boolean check(int cur) {

        for (int i = 0; i < cur; i++) {
            if (current[i] != after.charAt(i)) return false;
        }

        return true;
    }

    static void push(int cur) {
        if (current[cur - 1] == '1') current[cur - 1] = '0';
        else current[cur - 1] = '1';

        if (current[cur] == '1') current[cur] = '0';
        else current[cur] = '1';

        if (cur < N - 1) {
            if (current[cur + 1] == '1') current[cur + 1] = '0';
            else current[cur + 1] = '1';
        }
    }

    static void recur(int cur, int total) {

//        if (!check(cur)) return;

        if (cur == N) {
            if (check(cur)) answer = Math.min(answer, total);
            return;
        }

        if (current[cur - 1] != after.charAt(cur - 1)) {
            // 현재 스위치를 누른다.

            push(cur);
            recur(cur + 1, total + 1);

            // 복원
            push(cur);
        } else {
            recur(cur + 1, total);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        before = br.readLine();
        after = br.readLine();

        current = new char[N];
        for (int i = 0; i < N; i++) {
            current[i] = before.charAt(i);
        }

        // 1번 스위치 안 누르고 진행
        recur(1, 0);

        // 1번 스위치 누르기
        if (current[0] == '0') {
            current[0] = '1';
            current[1] = current[1] == '0' ? '1' : '0';
        } else {
            current[0] = '0';
            current[1] = current[1] == '0' ? '1' : '0';
        }
        recur(1, 1);

        if (answer == 1 << 30) {
            bw.write("-1");
        } else {
            bw.write(String.valueOf(answer));
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 16562. 친구비

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

문제 요약

• N명의 학생
• 학생 i에게 Ai만큼 돈을 주면 1달간 친구가 될 수 있다
• 총 k원의 돈으로 친구를 사귀려고한다.
• 단 친구를 사귀면 친구의 친구도 친구!
• 가장 적은 비용으로 모든 사람과 친구가되는 법은?

시간 제한

• 2초

입력

• 학생수 N, 친구 관계수 M, 가지고 있는 돈 k
  • 1≤N<1만
  • 0≤M≤1만
  • 1≤K≤1000만
• M개의 줄에 숫자 v, w가 주어짐
  • 학생 v , 학생 w가 친구라는 뜻
  • 기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수도 있다.

출력

• 준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력
• 없다면 Oh no 출력

접근법

결국 연결되어 있는 관계들 중 최솟값 비용만 더해가면 된다.

너무 union find에 집착X 몰라도 풀 수 있는 문제였다.

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M, K;
    static int[] cost;
    static int[][] relation;
    static boolean[] visited;
    static int min;

    static void dfs(int node) {
        visited[node] = true;
        min = Math.min(min, cost[node]);

        for (int i = 1; i <= N; i++) {
            if (visited[i] || relation[node][i] != 1) continue;

            dfs(i);
        }
    }

    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;

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

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

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

            relation[a][b] = 1;
            relation[b][a] = 1;
        }

        visited = new boolean[N + 1];
        int total = 0;
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                min = 1 << 30;
                dfs(i);
                total += min;
            }
        }

        if (total <= K) bw.write(String.valueOf(total));
        else bw.write("Oh no");
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2668. 숫자고르기

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

문제 요약

• 세로 두 줄, 가로 N개 칸으로 이루어진 표
• 첫째 줄 : 1,2, … , N이 차례대로 들어있고
• 둘째 줄 : 각 칸에 1이상 N이하 정수가 들어있다
• 첫째 줄에서 숫자를 적절히 뽑으면, 뽑힌 정수들의 집합과, 뽑힌 정수들의 바로 밑에 있는 정수들의 집합이 일치
• 위 조건을 만족하도록 정수들을 뽑되, 최대로 많이 뽑는 방법 찾기

시간 제한

• 1초

입력

• 첫째줄 : N이 주어짐
  • 1≤N≤100
• 둘쨰 줄 : 둘째 줄에 들어가는 정수가 한 줄에 하나씩 주어짐

출력

• 뽑힌 정수들의 개수를 출력
• 다음줄부터 오름차순으로 뽑힌 정수들을 한 줄에 하나씩 출력

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] arr;
    static boolean[] visited;
    static ArrayList<Integer> list = new ArrayList<>();

    static void dfs(int node, int start) {

        if (arr[node] == start) {
            list.add(start);
        }

        if (!visited[arr[node]]) {
            visited[arr[node]] = true;
            dfs(arr[node], start);
            visited[arr[node]] = 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));

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

        visited = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            visited[i] = true;
            dfs(i, i);
            visited[i] = false;
        }

        Collections.sort(list);
        
        StringBuilder sb = new StringBuilder();
        sb.append(list.size() + "\\n");
        for (Integer i : list) {
            sb.append(i+"\\n");
        }

        bw.write(String.valueOf(sb));
        bw.close();
        br.close();
    }
}