[python] (프로그래머스) 택배 배달과 수거하기

대회명/문제출처: 프로그래머스- 2023 KAKAO BLIND RECRUITMENT
https://school.programmers.co.kr/learn/courses/30/lessons/150369
유형: Greedy

<풀이방법>

1) ->는 배달 <- 픽업이라고 생각할 때, 가장 먼 곳부터 다녀오는게 맞다고 생각했고,

그럼 그리디 방법으로 풀어야한다고 생각했다. 

2) 완전탐색으로 풀까 하다가 새로 배열을 만들어서 푸는 것도 1억번을 넘지 않을 거라 생각해서, 새로 배열을 만들었다.

100,000*50=5,000,000

for i in range(n-1,-1,-1):
        if deliveries[i]!=0:
            delivery+=[i+1]*deliveries[i]
        if pickups[i]!=0:
            pickup+=[i+1]*pickups[i]

이런 식으로 해서 각 집위치를 횟수만큼 넣어줌

이러면 최댓값 비교해서 풀 수 있으니까???

 

그다음 while 문 돌면서 둘다 최대 idx 넘어갈 때까지 계산해줬다.

d=sum(deliveries)
p=sum(pickups)
now_p_idx,now_d_idx=0,0
while now_d_idx<d or now_p_idx<p:

answer에는 오고가고가 있으니까 *2 해줬고,

둘 중에 하나가 먼저 도착하는 경우를 생각해, if 문 넣어줌!

그저 2단계의 문제였다..

def solution(cap, n, deliveries, pickups):
    answer = 0
    delivery=[]
    pickup=[]
    for i in range(n-1,-1,-1):
        if deliveries[i]!=0:
            delivery+=[i+1]*deliveries[i]
        if pickups[i]!=0:
            pickup+=[i+1]*pickups[i]

    d=sum(deliveries)
    p=sum(pickups)
    now_p_idx,now_d_idx=0,0
    while now_d_idx<d or now_p_idx<p:
        if now_d_idx>=d: m=pickup[now_p_idx]
        elif now_p_idx>=p: m=delivery[now_d_idx]
        else: m=max(delivery[now_d_idx],pickup[now_p_idx])
        answer+=m*2
        now_d_idx+=cap
        now_p_idx+=cap
    return answer