오랜만입니다!
최근에는 운동, 면접 대비 CS 학습 및 프로젝트 정리, 개인 프로젝트 진행
PCCP 준비도 하면서 하루에 10문제 이상 풀고 있기 때문에
블로그에 모두 정리하기 어려워서 잠시 쉬었었습니다 ㅎㅎ..
백준이나 프로그래머스에서 문제를 많이 풀다가
최근 정올에서 단계별 문제를 풀고 있는데
이미 풀었던 문제들도 다시 풀어보니 접근 조차 어려웠던 문제들이 있었습니다.
특히 다른 문제들보다 그리디 문제들이 문제를 풀고 난 후 발상을 떠올리기가 어려웠습니다.
그래도 원리를 이해하고 나면 구현하는 것은 어렵지 않았기 때문에
풀면서 발상하기 어려웠던 문제들을 정리하고자 합니다.
문제 정의
- 책꽂이를 만들기 위한 널빤지 개가 필요하며 각 널빤지의 길이는 로 주어짐
- 필요한 널빤지들을 구하기 위해 하나의 큰 널빤지를 구매해 잘라서 사용하고자 함
- 길이는 정확하게 로 구매
- 톱을 대여하는데는 자르기 전 길이를 비용으로 지불
하나의 긴 널빤지를 잘라서 필요한 널빤지들로 모두 자르기 위한 최소 비용을 구해라
접근 방법
초기 접근 방법
처음에는 Top-down으로 널빤지들을 우선순위 큐에 넣고
필요한 널빤지의 길이를 가장 큰 순서부터 잘라내는 방식을 사용했었습니다.
하지만 정답을 출력 후 이 방법은 정답이 아니라는 것을 알게 되었습니다.
왜냐하면 비용 지불 방법이 "자르기 전 길이"만큼 부과되기 때문에
한 번 자를 때 최대한 절반에 가깝게 잘라야 그리디하게 자를 수 있다는 것을 알게 되었습니다.
하지만 제가 생각한 Top-down 방식으로는 절대 문제를 해결할 수 없다는 것을 깨닫게 되었습니다.
(중얼중얼)
현재 자르는 하나의 긴 널빤지에 필요한 널빤지들의 길이를 조합해서 최대한 절반에 가깝게 나누고
이후 두 개로 나눠진 긴 널빤지를 필요한 널빤지들의 길이를 조합해서... 이걸 하나의 널빤지가 될때까지 반복해야하며 절반에 가장 가까운 널빤지 길이 조합을 찾고 이 긴 널빤지는 어떤 길이의 작은 널빤지들을 잘라내기 위한 널빤지인지 상태도 저장해야되고..
현실적으로 불가능하다는 판단을 하게 되었습니다.
실제로 잘라볼 수 없다면서 어떻게 해결하는건데?
Bottom-up 문제 해결
이 문제는 하나의 긴 널빤지를 잘라나가는 것이 아니라
작은 널빤지들을 합쳐가면서 최소 비용을 찾는 것이 핵심입니다.
자르기 전 길이로 계산한다 = 두 개의 작은 널빤지를 합친 후 계산한다
위와 같이 치환을 한다면 Optimal File Merge Patterns로 해결 가능합니다.
파일 합치기 문제에서 풀었던 것과 같이 이 방법이 항상 최적해를 보장하기 때문에
이 방법으로 문제를 해결할 수 있습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PriorityQueue<Integer> pq = new PriorityQueue<>();
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
int L = Integer.parseInt(br.readLine());
pq.offer(L);
}
long cost = 0;
while (pq.size() > 1) {
int sum = pq.poll() + pq.poll();
cost += sum;
pq.offer(sum);
}
System.out.println(cost);
}
}