[백준] 그리디 문제 풀이 (백준 1931, 11399, 1541)

📌 핵심 요약

• 백준 1931 회의실 배정 — 종료 시간 오름차순 정렬 후 탐욕적으로 선택. 종료 시간이 같으면 시작 시간 기준으로 2차 정렬
• 백준 11399 ATM — 인출 시간을 오름차순 정렬 후 누적합을 구해 합산. 짧은 사람을 앞에 세울수록 총 대기시간 최소
• 백준 1541 잃어버린 괄호 — 첫 번째 마이너스 이후 등장하는 모든 수를 빼면 최솟값. "-" 기준으로 split 후 각 그룹을 합산

 

목차

1 1931 — 회의실 배정

풀이 아이디어

Java 코드

2 BOJ 11399 — ATM

풀이 아이디어

Java 코드

3 BOJ 1541 — 잃어버린 괄호

풀이 아이디어

Java 코드

 

1 백준 1931 — 회의실 배정

백 #1931

회의실 배정

N ≤ 100,000 · 시간제한 2초

난이도: Silver I

회의실이 하나뿐일 때, 겹치지 않게 회의를 최대한 많이 배정하라. 각 회의는 시작 시간과 종료 시간이 주어지며, 시작 시간과 종료 시간이 같을 수 있다.

풀이 아이디어

종료 시간이 빠를수록 다음 회의를 선택할 기회가 더 많아진다. 일찍 끝나는 회의를 선택하면 남은 시간이 최대한 길게 보존되어, 그 안에 더 많은 회의를 넣을 수 있다.

💡

교환 논증으로 정당성 증명

최적해에서 회의 X를 선택했는데 X보다 일찍 끝나는 Y가 있다면, X를 Y로 바꿔도 이후 선택 가능한 회의가 줄어들지 않는다. 따라서 일찍 끝나는 회의를 먼저 선택하는 것은 항상 안전하다.

⚠️

정렬 기준이 2개!

종료 시간만으로 정렬하면 시작 시간이 늦은 회의가 먼저 와서 손해를 볼 수 있다. 1순위: 종료 시간 오름차순 / 2순위: 시작 시간 오름차순으로 정렬해야 한다.

예제 추적

회의 (시작, 종료)	선택 여부	이유
(1, 4)	선택	end=0 ≤ 시작=1 → 선택, end=4
(3, 5)	패스	end=4 > 시작=3
(0, 6)	패스	end=4 > 시작=0
(5, 7)	선택	end=4 ≤ 시작=5 → 선택, end=7
(3, 8)	패스	end=7 > 시작=3
(5, 9)	패스	end=7 > 시작=5
(6, 10)	패스	end=7 > 시작=6
(8, 11)	선택	end=7 ≤ 시작=8 → 선택, end=11
(8, 12)	패스	end=11 > 시작=8
(2, 13)	패스	end=11 > 시작=2
(12, 14)	선택	end=11 ≤ 시작=12 → 선택, end=14

총 4개 선택 ✅

풀이 과정

1. 회의 배열을 (종료 시간, 시작 시간) 기준으로 정렬한다
2. end = 0, count = 0 으로 초기화한다
3. 회의를 순서대로 보면서 시작 시간 ≥ end 이면 선택: end를 현재 종료 시간으로 갱신, count++
4. count를 출력한다

Java 코드

 

Java — 백준 1931 회의실 배정

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));
        int n = Integer.parseInt(br.readLine().trim());

        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken()); // 시작 시간
            arr[i][1] = Integer.parseInt(st.nextToken()); // 종료 시간
        }

        // 1순위: 종료 시간 오름차순 / 2순위: 시작 시간 오름차순
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[1] == o2[1]) return o1[0] - o2[0];
            return o1[1] - o2[1];
        });

        int count = 0;
        int end   = 0; // 마지막으로 선택한 회의의 종료 시간

        for (int i = 0; i < n; i++) {
            if (arr[i][0] >= end) { // 시작 시간 >= 현재 끝 시간이면 선택
                end = arr[i][1];
                count++;
            }
        }

        System.out.print(count);
    }
}

2백준 11399 — ATM

백준 #11399

ATM

N ≤ 1,000 · Pi ≤ 1,000 · 시간제한 1초

난이도: Silver IV

ATM 앞에 N명이 줄을 서 있다. 각 사람이 돈을 인출하는 데 걸리는 시간 Pi가 주어질 때, 각 사람의 대기 시간 합의 최솟값을 구하라.

풀이 아이디어

인출 시간이 짧은 사람을 앞에 세울수록, 뒤에 오는 사람들이 기다리는 시간이 줄어든다. 따라서 인출 시간 오름차순 정렬 후 누적합을 합산하면 최솟값을 구할 수 있다.

ℹ️

각 사람의 대기 시간 공식

i번째 사람의 총 대기 시간 = P[1] + P[2] + ... + P[i] (앞 사람들 시간 + 자기 시간) 즉, 누적합 sum을 유지하면서 매 단계마다 count에 더해주면 된다.

예제 추적 — 정렬 후: [1, 2, 3, 3, 4]

i	arr[i]	sum (누적)	count (합산)
0	1	1	1
1	2	3	4
2	3	6	10
3	3	9	19
4	4	13	32 ✅

풀이 과정

1. 인출 시간 배열을 한 줄에서 StringTokenizer로 읽는다
2. 오름차순 정렬한다
3. sum과 count를 0으로 초기화하고, 순서대로 sum += arr[i], count += sum을 반복한다
4. count를 출력한다

Java 코드

 

Java — 백준 11399 ATM

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));
        int n = Integer.parseInt(br.readLine().trim());

        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine()); // 한 줄에 전부!
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr); // 짧은 사람부터 세우기

        int sum   = 0; // i번째 사람까지 걸리는 누적 시간
        int count = 0; // 최종 정답
        for (int i = 0; i < n; i++) {
            sum   += arr[i]; // 이 사람이 끝날 때까지 시간
            count += sum;    // 이 사람의 총 대기시간을 합산
        }

        System.out.print(count);
    }
}

3백준 1541 — 잃어버린 괄호

백준 #1541

잃어버린 괄호

식 길이 ≤ 50 · 시간제한 2초

난이도: Silver II

양수와 +, -로 이루어진 식에 괄호를 적절히 쳐서 값을 최소로 만들어라. 괄호를 몇 번이든 원하는 위치에 칠 수 있다.

풀이 아이디어

핵심 관찰: "-" 이후에 오는 모든 "+"는 괄호로 묶으면 전부 "-"로 바꿀 수 있다.

ℹ️

예시

55 - 50 + 40 → 55 - (50 + 40) = 55 - 90 = -35
10 - 20 + 30 + 40 → 10 - (20 + 30 + 40) = 10 - 90 = -80

따라서 "-"를 기준으로 식을 쪼개면 여러 그룹이 생기고, 첫 번째 그룹만 더하고 나머지 그룹은 전부 빼면 최솟값이 된다. 각 그룹 안에는 "+"로 연결된 숫자들이 있으므로 추가로 쪼개서 합산한다.

입력	"-" split 결과	계산	정답
55-50+40	["55", "50+40"]	55 - (50+40)	-35
10+20+30+40	["10+20+30+40"]	10+20+30+40	100
00009-00009	["00009", "00009"]	9 - 9	0

⚠️

첫 번째 그룹에도 "+"가 있을 수 있다!

"10+20+30-40"처럼 첫 그룹이 "10+20+30"인 경우, Integer.parseInt("10+20+30")은 NumberFormatException을 발생시킨다. 첫 번째 그룹도 반드시 "\\+"로 split해서 합산해야 한다.

풀이 과정

1. 입력 문자열을 "-" 기준으로 split해서 그룹 배열을 만든다
2. 첫 번째 그룹을 "+" 기준으로 다시 split해서 합산 → result 초기화
3. 나머지 그룹(인덱스 1 이상)을 "+" 기준으로 split해서 합산 → result에서 빼기
4. result를 출력한다

Java 코드

 

Java — 백준 1541 잃어버린 괄호

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String n = br.readLine().trim();

        String[] s = n.split("-"); // "-" 기준으로 그룹 분리

        // 첫 번째 그룹: "+"로 쪼개서 합산
        int count = 0;
        for (String p : s[0].split("\\+")) {
            count += Integer.parseInt(p);
        }

        // 나머지 그룹은 전부 빼기
        for (int i = 1; i < s.length; i++) {
            for (String p : s[i].split("\\+")) {
                count -= Integer.parseInt(p);
            }
        }

        System.out.print(count);
    }
}

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.