코테 문제풀이 9일차

👑문제: [Programmers_Kakao_Blind_Recruitment]

택배배달과 수거하기

문제 설명

cap만큼의 짐을 실을 수 있는 트럭이 택배들을 배달하고 수거할 때 거쳐야 하는 최단 거리를 구하기

풀이 시 고려해야 할 점

1. 배달과 수거를 독립적으로 생각해야 한다.
   -> 어자피 수거하러 가는 길에 배달을 병행할 수 있으므로 둘 중에 더 긴 거리에 있는 것을 정답에 추가시켜야 한다.
2. for문을 마지막부터 돌아야 한다.
   -> 가장 먼 거리부터 배달 or 수거를 돌아야 하기 때문

풀이 과정

class Solution {
static public long solution(int cap, int n, int[] deliveries, int[] pickups) {
    long answer = 0;
    int pickUp = 0;
    int deliver = 0;
    for (int i = n - 1; i >= 0 ; i--) {
      pickUp += pickups[i];
      deliver += deliveries[i];
      while(pickUp > 0 || deliver > 0) {
        pickUp -= cap;
        deliver -= cap;
        answer += (i+1) * 2;
      }
    }
    return answer;
  }
}

느낀점

배달과 수거를 분리하는 개념이 이해가 안가서 둘 중 더 큰 값이 존재할 때의 각각의 경우를 모두 나누어서 풀었었는데, 시간 초과에다가 거의 다 틀린채로 결과를 받았다
가장 먼 거리에 있는 것이 cap보다 엄청 큰 경우를 가장 고민을 많이했는데, 이를 누적합으로 풀면 쉽게 풀린다는 것을 깨닫고 나서 수월하게 풀 수 있던 것 같다.
오랜만에 푸니까 알고리즘 다 까먹은 것 같아서 백준으로 다시 돌려야겠다!