문제 - 라면 공장

 

# 문제 

Q. 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 

원래 밀가루를 공급받던 공장의 고장으로 앞으로 

k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 

라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 

원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 

밀가루가 떨어지지 않고 공장을 운영하기 위해서 

최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환 하시오.

dates[i]에는 i번째 공급 가능일이 들어있으며, 

supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

 

 

# 예시

stock = 4
dates = [4, 10, 15]
supplies = [20, 5, 10]
k = 30

# 다음과 같이 입력값이 들어온다면,
# 현재 재고가 4개 있습니다. 그리고 정상적으로 돌아오는 날은 30일까지입니다.
# 즉, 26개의 공급량을 사와야 합니다!
# 그러면 제일 최소한으로 26개를 가져오려면? supplies 에서 20, 10 을 가져오면 되겠죠?
# 그래서 이 경우의 최소 공급 횟수는 2 입니다!

 

# 문제 풀이 

 

풀긴 했지만 코드가 매우 더러웠다..

내가 생각했던 방법은 해당 날짜로 이동하는 방법으로 갔다. 

 

처음에는 어차피 경우의 수를 구하는 거니 앞에서 진행했던 더하거나 빼거나  문제처럼 재귀함수를 통해 모든 경우의 수를 파악하여 수가 가장 작은 리스트를 반환하려하였지만 그때 당시 아직 재귀함수에 대한 이해가 되질 않아 함수 제작에 어려움을 느끼다가 푸는 방식만 확인하기 위해 답안을 확인했었다. 

 

답안을 확인하자 역시 충격을 먹었는데  경우의 수를 파악하는 방법이 아닌 날짜를 이동하는 방법으로 진행이 됬다. 

 

리스트를 순회하면서 현재 남아있는 재고량 보다 같거나 적은 보급날짜을 모아서 

그 중에 가장 큰 보급량을 선택한다면 가장 적은 횟수로 많은 보급을 챙길 수 있기 때문에 해당 방법을 통해 문제를 푸는 것이였다. 

해당 답안을 보며 이해가 되질 않았던 부분도 있었는데 전체 보급량을 기준으로 수를 셌다는 것이다. 

 

처음에 방법을 파악하기 위해 예시를 적어가며 진행을 했었는데 

 

오늘 4개가 남았다면 첫번째 원소인 4일에 보급을 받아야만한다. 

즉 4일에 보급을 받는 날이되면 기존의 4개가 소비되고 새로 보급받은 20개가 있어서 남은 수량은 20개가 되어야한다. 

 

하지만 코드는 이부분의 숫자가 24개가 되어있어서 이부분을 이해하는데 시간이 오래걸렸던 것같다. 남은 수량 파악도 4일째 되는 날이면 남은 양이 20이되므로 보급날짜를 21일로 추가한 다른 케이스로 진행했을 때도 값이 달리 나왔었다. 

그래서 더더욱 헷갈렸던 것같다. 

 

결론은 오늘날을 기준으로 남은 수량이 34가 되게끔 남은 수량보다 적은 보급일들 중 가장 큰값을 선택해 나가면 되는 것이다 .

 

---