문제 링크

문제링크

문제 설명

제한사항

입출력 예

입출력 예 설명은.. 링크 참조해주세요 ㅎ.ㅎ

풀이

1. 뒤에서부터 물량을 최대한 소화하기위해 뒤에서부터 시작한다.
   1-1 뒤에서부터 처리해야하는 이유는 난 이렇게 생각한다.
   1-2 앞에서부터 물건을 소화하다가 뒤에가가지고 자투리 잉여 물량이 남아버리면 그 먼거리를 가야한다.
   1-3 그냥 탐색 순서만 뒤에서 앞으로하면 같은 상황이 발생했을때 짧은 거리를 왔다갔다하면 되니, 이게 최솟값이다
2. 뒤에서부터 들 수 있는 용량만큼 제거해나가자. (배달과 수거 각각)

일단 그리디로 분류는 했지만 나는 그냥 구현으로 푼 것 같다 ㅋㅋ

풀고나서는 음.. 왜 시간초과가 안났지..? 싶은 코드긴하다..

택배들을 지워나갈때 일단 물량만큼 한번에 빼는 방식은 괜히 if문이 많이 발생하는것같아서 일단 시간초과를 날 것을 예상하고 물량을 하나씩 --했는데 시간초과가 안남..!! (코드를 보면 알겠지만 반복문이 좀 많다)

내 생각에 시간복잡도 그래프가 바뀔 수준의 for문을 호출하는 것이 아니라, 처음과 끝이 정해진 반복문만을 돌렸기때문일까 생각한다.

풀었는데도 찝찝한 문제다.. 다시 풀어보아야겠다!

코드

import java.util.*;
class Solution {
    
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        boolean comhere = false;
        int i, j;
        for(i = n - 1, j = n - 1; i >= 0 || j >= 0; ) {
            int box = cap;
            for(; i >= 0 && deliveries[i] == 0; i--);
            for(; j >= 0 && pickups[j] == 0; j--);
            int nowPos = Math.max(i, j);
            comhere = false;
            if(i >= 0) { //배달할 곳이 있으면
                while(box > 0 && i >= 0) {
                    box--;
                    deliveries[i]--;
                    if(deliveries[i] == 0)
                    {
                        for(; i >= 0 && deliveries[i] == 0; i--);
                    }
                }
                comhere = true;
            }//가는길에 떨줘주고
            box = 0; //이제 배달해줄 곳이 없으면 아예 들고나오면 안됨
            if(j >= 0) { //수거할 곳이 있으면
                while(box < cap && j >= 0) {
                    box++;
                    pickups[j]--;
                    if(pickups[j] == 0)
                    {
                        for(; j >= 0 && pickups[j] == 0; j--);
                    }
                }
                comhere = true;
            }
            if(comhere) {
                answer = answer + (long) (nowPos + 1) * 2;
            }        
        }
        return answer;
    }
}