(Baekjoon) GreedyAlgorithm - (26) 택배

8980번: 택배

---

 

  오름차순으로 정렬하고 따져보니 너무 복잡하다고 생각이들어서 답이 안나오길래 결국 해답을 찾아보았다.

우선 개념에 대한설명은 아래 긴글을 참고 두번째 블로그는 해당개념을 사용하여 코딩한것이다.

https://www.acmicpc.net/board/view/6327

https://steadev.tistory.com/15

 

블로그에 나와있는것을 참고했으며 그리디 알고리즘인것에 비해서 이해하기가 까다롭다. 직관적이라는 느낌이 강하다.

문제를 조금씩 풀다보니까 대부분의 알고리즘 문제가 오름차순을 사용하는것이 첫 시작인것같다.

---

핵심개념을 설명하자면 "각 마을에서 트럭은 남은공간이 최소가 될때 최대한 많은 곳에 배달할수있다." 입니다.

그러니까 최대한 마을전체적으로 보았을때 남은공간을 최소하여야만 최대한 많이 배달할수 있다는뜻입니다.

 

처음에는 초기값을 마을이 4개가 있을경우 전부 40으로 준다고 생각하면은 각마을마다 다음과 같이 40의 여유분이 있는것입니다.

1	2	3
40	40	40

이제 이곳에서 남은공간을 최대한 0에 가깝게 만들기 위해서는 앞에서부터 값을 줄이면 되겠지요?

그렇기 때문에 도착점을 기준으로 오름차순 시작점을 기준으로 오름차순으로 정렬하는것입니다.

직감적으로 보았을때 그렇습니다. 그렇기 때문에 도착점을 기준으로 앞에서부터 빼야됩니다. 왜냐하면 출발점이 1번 마을이기 때문입니다.

(이 부분이 이해하기가 살짝 난해합니다.)

마지막 마을(4번째)을 포함시키지 않고 진행하는것은 a에서 b로 옮긴다고 하였을때 a 이상 b미만 이기 때문에 b는 포함하지 않기 때문에

마지막마을은 따질 필요가 없는것입니다.

(a마을과 b마을 사이에 a이상 b미만으로 처리하는것은 도착점에서는 물건을 내려놓기 때문입니다.)

아래블로그도 비슷한 개념인데 저는 저처럼 푸는것이 더 쉬운것같기도하고 사람마다 다르니 푸는방법은 알아서 선택하시면 될것같습니다.

백준 8980번 택배

 

 

다음은 제출후 다른 사람과 비교하면서 수정해본결과다.

BufferedReader가 빠르다는것은 알고있었지만 이렇게 차이가 나는줄은 몰랐다. 특히 메모리부분은 왜저렇게 차이나는지는 모르나 아마

Buffer를 사용하기 때문에 메모리가 상당히 줄어든것같다.

 

그리고 올림피아드 문제는 아래에서 테스트케이스를 확인해볼수 있다고 한다. 나도 한번 써봐야겠다.

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1903&sca=50&sfl=wr_subject&stx=%ED%83%9D%EB%B0%B0&sop=and

JUNGOL | 택배 > 문제은행

 

package GreedyAlgorithm;

import java.util.Comparator;
import java.util.StringTokenizer;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class _8990{
    
    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int Town = Integer.parseInt(st.nextToken());
        int Truck_Size = Integer.parseInt(st.nextToken());
        int Box_Info = Integer.parseInt(br.readLine());
        int Box_Info_AtoB_Weight[][] = new int[Box_Info][3];
        int Town_leftSpace[] = new int[Town + 1];
        Arrays.fill(Town_leftSpace, Truck_Size);

        for (int i = 0; i < Box_Info; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 3; j++) 
                Box_Info_AtoB_Weight[i][j] = Integer.parseInt(st.nextToken());    
        }

        Arrays.sort(Box_Info_AtoB_Weight, new Comparator<int[]>() {
            public int compare(int[] back, int[] forth) {
                return back[1] == forth[1] ? back[0] - forth[0] : back[1] - forth[1];
            }
        });
            
        int Box_Count_Moved = 0;
        int Min_Space=0;
        int Min_Compare=0;

        for (int i = 0; i < Box_Info_AtoB_Weight.length; i++) {
            Min_Space = Truck_Size;
            for (int j = Box_Info_AtoB_Weight[i][0]; j < Box_Info_AtoB_Weight[i][1]; j++)
                if(Min_Space > Town_leftSpace[j]) Min_Space = Town_leftSpace[j];

            if(Min_Space>0){
                Min_Compare = Math.min(Box_Info_AtoB_Weight[i][2], Min_Space);
                Box_Count_Moved += Min_Compare;
                for (int j = Box_Info_AtoB_Weight[i][0]; j < Box_Info_AtoB_Weight[i][1]; j++)
                    Town_leftSpace[j] -= Min_Compare;
            }
        }

        System.out.println(Box_Count_Moved);


    }

}

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study