(JAVA) 백준 8980번 : 택배

 

https://www.acmicpc.net/problem/8980

8980번: 택배

 

그리디 알고리즘 문제 중 하나인 택배 문제.

 

처음에 가볍게 접근했다가 몇 시간을 허비하고 결국 힌트를 통해 접근법을 찾았다.

 

 

가볍게 접근이란

 

마을 별로 index를 만들어서 마을마다 박스를 싣는 경우와 박스를 내리는 경우 모두를 더해 저장한 다음

1번 마을부터 순차적으로 방문해서 더하고 빼는 방법으로 진행했었다.

 

 

이러다가 어떤 예외에서 틀린 건지 허비할 뻔 했으나

** 팁 : 자신이 이 문제의 어떤 테스트케이스에서 틀렸는지 확인하고 싶으면 JUNGOL에 소스 코드를 제출해보자. 

여기서와 백준에서의 문제 번호는 다르나 대회 기출 문제들은 어느정도 있기에 검색해서 찾아내면 좋을듯 싶다.

참고로, 회원가입과 로그인은 필수다.

http://www.jungol.co.kr/

 

 

명쾌한 힌트를 보고 접근 방법을 약간 다르게 변형시켜 문제를 풀 수 있었다.

 

 

매커니즘

---

문제 접근을 바꿔보자.

 

 

1. 마을 별로 내리는 짐의 개수 대신에 마을에 방문해서 짐을 내린 후 트럭에 싣고 있는 박스의 개수를 파악해보자.

 

2. 보내는 마을과 받는 마을의 거리가 멀수록 보내는 마을부터 다음 마을들을 순차적으로 방문할 때마다 받는 마을 바로 직전의 마을까지 그 짐을 계속 들고 있어야 한다.

 그 사이에 더 큰 짐을 싣고 내릴 수 있기 때문에 보내는 마을과 받는 마을의 거리가 멀면 상당히 비효율적이다.

 

3. 문제에서는

 무조건 1번 마을부터 N번 마을까지 순차적으로 방문한다는 조건

 보내는 마을보다 무조건 받는 마을의 번호가 높다는 조건

이 두 조건을 활용하는 것으로 문제를 풀 수 있다.

 

그렇다면,

보내는 마을이 받는 마을과 거리가 가깝다는 뜻은

받는 마을의 번호를 오름차순으로 정렬했을 때 가장 앞에 있을수록 가깝다는 뜻이 된다.

그 다음 우선순위로는 보내는 마을을 오름차순으로 정렬하는 것이다.

** 두 번째 우선순위는 굳이 안해도 풀 수 있다.

 

 

즉, 해결 방법은

 1) 각 마을 별로 박스의 개수를 파악할 수 있는 Array 생성

 2) 받는 마을 번호를 오름차순으로 정렬

  ex) 백준 예제

받는 마을을 정렬한다면

 

1 2 10

2 3 10

1 3 20

3 4 20

2 4 20

1 4 30

이 된다.

 

3) 밑의 진행 방법을 보고 알고리즘 짜면 됨.

** 밑에 소스 코드 있움!

 

 

 - 앞에서부터 (보내는 마을, 받는 마을, 박스 개수) 를 꺼내서 사용

** 참고로, 받는 마을에서 박스 개수는 고려하지 않는다. 도착하면 박스를 내리기 때문에

 

 

 

1번 째 꺼낸 경우

                                                     트럭의 용량 :   40

                                                              마을 :    1  //  2  //  3  //  4

                        마을에서의 트럭에 싣은 박스 개수 :   10 //  0 //   0  //  0   ( +10 내림 = 10)

 

 

 

2번 째 꺼낸 경우

                                                     트럭의 용량 :   40

                                                              마을 :    1  //  2  //  3  //  4

                        마을에서의 트럭에 싣은 박스 개수 :   10 //  10 //   0  //  0  ( + 10 내림 = 20)

 

 

 

3번 째 꺼낸 경우

                                                     트럭의 용량 :   40

                                                              마을 :    1  //  2  //  3  //  4

                        마을에서의 트럭에 싣은 박스 개수 :   30(+20) //  30(+20) //   0  //  0  ( + 20 내림 = 40)

 

 

 

4번 째 꺼낸 경우

                                                     트럭의 용량 :   40

                                                              마을 :    1  //  2  //  3  //  4

                        마을에서의 트럭에 싣은 박스 개수 :   30 //  30 //   20(+ 20) //  0  ( + 20 내림 = 60)

 

 

 

5번 째 꺼낸 경우

                                                     트럭의 용량 :   40

                                                              마을 :    1  //  2  //  3  //  4

                        마을에서의 트럭에 싣은 박스 개수 :   30 //  40(+10) //   30(+ 10) //  0  ( + 10 내림 = 70)

 

** 트럭의 용량이 40이기 때문에 2번 마을에 박스가 20개나 있음에도 불구하고 10만 싣을 수 있다.

** 3번 마을에는 2번에서 10만 싣었으니 당연히 10이 추가된다.

 

 

 

6번 째 꺼낸 경우

                                                     트럭의 용량 :   40

                                                              마을 :    1  //  2  //  3  //  4

                        마을에서의 트럭에 싣은 박스 개수 :   30 //  40 //   30  //  0  ( + 0 내림 = 70)

 

 

따라서, 최대 박스는 70이 된다!!!!!!

 

이런 방식으로 계산하는 알고리즘을 짜서 문제를 풀어보셨으면 좋겠습니다.

 

감사합니다!

 

 

 

소스 코드

---

package greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

// 택배 문제
// 그리디 알고리즘
public class p8980 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.valueOf(st.nextToken());
		int truck = Integer.valueOf(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int m = Integer.valueOf(st.nextToken());
		
		int[] boxs = new int[n + 1]; // 인덱스 : 1 ~ n까지. 해당 index 마을에 도착했을 때의 트럭에 담은 박스 개수
		ArrayList<Town> towns = new ArrayList<Town>();
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.valueOf(st.nextToken());
			int to = Integer.valueOf(st.nextToken());
			int box = Integer.valueOf(st.nextToken());
			towns.add(new Town(from, to, box));
		}
		
		Collections.sort(towns);	// 받는 마을 오름차순 정렬
		
		int boxCount = 0;
		for(Town town : towns) {
			int start = town.start;
			int end = town.end;
			int box = town.box;
			
			int max = 0;
			boolean isLoad = true;
			for(int i = start; i < end; i++) {
				if(boxs[i] >= truck) {
					isLoad = false;
					break;
				}
				max = Math.max(max, boxs[i]);
			}
			
			if(isLoad) {
				int unloads = truck - max;
				if(unloads > box) {
					unloads = box;
				}
				boxCount += unloads;
				
				for(int i = start; i < end; i++) {
					boxs[i] += unloads;
				}
			}
		}
		System.out.println(boxCount);
	}
}

class Town implements Comparable<Town> {
	int start;
	int end;
	int box;
	
	Town(int start, int end, int box) {
		this.start = start;
		this.end = end;
		this.box = box;
	}

	// 오름차순 정렬을 위한 Comparable 클래스 함수 사용
	@Override
	public int compareTo(Town town) {
		if(this.end < town.end) {	
			return -1;
		}
		else if(this.end == town.end){
			return 0;
		}
		else {
			return 1;	
		}
	}
}

 

 

깃허브에서 전체 소스코드 보기