[1스4코2파] #123. LV 2. 택배 배달과 수거하기

gunny·2023년 5월 6일

1스4코2파 코딩테스트 코딩테스트 python 프로그래머스 택배 배달과 수거하기 프로그래머스 택배 배달과 수거하기 python

코딩테스트

목록 보기

124/530

[1스4코1파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코2파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (123일차)
[4코1파] 2023.01.13~ (114일차)
[1스4코1파] 2023.04.12~ (25일차)
[1스4코2파] 2023.05.03 ~ (4일차)

Today :

2023.05.06 [123일차]

프로그래머스 LV 2
택배 배달과 수거하기
https://school.programmers.co.kr/learn/courses/30/lessons/150369

문제 설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

배달 및 수거할 재활용 택배 상자 개수

배달 및 수거 과정

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ cap ≤ 50
1 ≤ n ≤ 100,000
deliveries의 길이 = pickups의 길이 = n
deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
0 ≤ deliveries의 원소 ≤ 50
0 ≤ pickups의 원소 ≤ 50
트럭의 초기 위치는 물류창고입니다.

입출력 예

입출력 예 설명

입출력 예 #1
문제 예시와 동일합니다.

입출력 예 #2
배달 및 수거할 재활용 택배 상자 개수

배달 및 수거 과정

30(=7+7+5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.
따라서, 30을 return 하면 됩니다.

문제 풀이 방법

일단 짧은거리로 가기 위해서는 주어진 n의 집에서
가장 먼 곳부터 해치워야 하기 때문에, 가장 먼 곳부터 배달하고 없애고 조져야한다. 그래서 n에서부터 원점까지로 Loop를 돌렸음.
그리고 나서 이 cap을 핸들링했어야 했는데, 여기서 사실 막혔다.

cap을 -= 하다가 이게 아닌 것 같아서 머리를 쥐어짜다가
어쩔 수 없지 치트키 검색하기 프로그래머스 택배 배달과 수거하기 python ...

처음 생각했던 것처럼 원점에서 가장 먼 곳부터 loop를 도는데,
딜리버리와 픽업의 개수를 센다음에,
while 문으로 주어진 cap을 빼주면서 거기서 0보다 낮아질 때까지
횟수를 2배한다.. 왕복이라서 i만큼 2배로..

생각보다 쉬운 풀이었는데.. 이걸 생각해내는게 진짜 어렵다는 말이지

내 코드

def solution(cap, n, deliveries, pickups):
    answer, delCnt, picCnt = 0, 0, 0
    for i in range(n-1, -1, -1):
        delCnt += deliveries[i]
        picCnt += pickups[i]
        
        while delCnt >0 or picCnt>0:
            delCnt -= cap
            picCnt -= cap
            answer += 2*(i+1)
    
    return answer

증빙