[C++] 택배 배달과 수거하기 (프로그래머스 LEVEL 2)

https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

---

문제풀이

고민하다가 방법이 잘 떠오르지 않아 다른 사람의 풀이를 봤다. 너무 쉽게 풀었다. 비슷한 접근을 하고 있었는데 조금 더 고민해볼걸 그랬다 라는 생각이 들었다.

 

1. 배열의 뒤에서 부터 탐색하며 각 값을 변수에 더해준다.

2. 각각 더한 변수의 값이 하나라도 0이상이라면, 계속해서 cap 만큼을 빼준다.

3. 빼는 행위를 할 때는 정답값을 더해준다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    int go = 0, back = 0;
    for(int i=n-1; i>=0; i--) {
        go += deliveries[i];
        back += pickups[i];
        
        while(go > 0 || back > 0) {
            go -= cap;
            back -= cap;
            answer += (i+1)*2;
        }
    }
    return answer;
}

go에는 현재 인덱스의 배달해야 되는 택배 수가 더해진다.

back에는 현재 인덱스의 가져가야 하는 택배 수가 더해진다.

 

만약 둘 중 어느 값이라도 0보다 크다면, 해당 위치에서 반드시 배달, 혹은 수거를 해야한다. 그러므로 최대값 만큼 각각 빼주는 것이다. cap만큼 빼주더라도 다시 와야할 수 있기 때문에 while을 돌렸다. 사실 while 말고 그냥 수식으로 계산해도 된다. 몫과 나머지를 사용하면 한번에 구할 수 있다.

이러면 go, back이 음수가 될수 있는데, 그 이유는 현재 위치보다 앞에 있는 택배까지 배달, 수거할 수 있기 때문이다. 이렇게 하면 인덱스가 작아졌을 때 이전 번 택배 배달, 수거와 함께 처리 한다고 생각하면 된다.

 

참고

https://oh2279.tistory.com/147