Question

도저히 모르겠으면 나이스한 해설 보러 오세용

필자는 생각합니다.
카카오가 코테의 수준을 너무나도 높여버렸습니다.

이젠 레벨2와 레벨3의 구분이라는 것이 있는지 모르겠습니다.

난이도가 다 레벨3이 된 것 같은 기분은 저만 드는 것일까요?

cap만큼의 공간을 사용하여, 배달도 수행하고, 회수도 수행해야 합니다.

이 문제를 풀기위한 당연한 기준들을 한 번 정리해보려고 합니다.

배달할 물건이나, 회수할 물건이 i번째 까지 존재한다면, 당신은 반드시 i번째 까지는 적어도 한 번은 가야합니다.
한 번 출발하여, 물류창고로 돌아오면, cap만큼의 배달을 수행할 수 있고, cap만큼의 물건을 회수 해 올 수 있습니다.
한 곳에서 택배를 전부 배달하지 못했거나, 회수하지 못했다면, 당신은 물류창고로 돌아왔다가, 다시 같은 장소로 떠나야 합니다.

아마, 이 문제들을 심히 고민해보았다면, 3가지의 정의는 내릴 수 있어야 합니다.

그리고 2번 정의에 따라, 물건의 전달이나, 물건의 회수는 항상 최대 cap만큼 수행 할 수 있다는 사실을 알 수 있습니다.

아마, 이해가 되지 않을 수 있습니다. 전달해야 할 물건이 너무 많아서 회수가 불가능한 상황이 생길 수 있지 않느냐고 말이죠.

하지만, 그 문제는 배열을 거꾸로 탐색하면 쉽게 해결 할 수 있습니다.

1번 정의에 따라, 당신은 반드시 전달할 물건이나, 회수할 물건이 있는 장소까지는 도달해야 합니다.

거꾸로 배열을 탐색한다는 의미는, 이미 방문이 가능한 모든 지점들을 왕복했다는 가정하에 문제를 풀게 됩니다.

물류창고에서, 목적지 까지 가는데, 택배가 너무 많아 회수가 불가능 하였다면, 돌아올 때는 이미 모든 장소를 한 번씩 들렸기에,

트럭에 물건이 비어있게 됩니다. 이 때 회수하면 됩니다.

이로써 이런 정의들을 단순화 시켜보자면, 사실 물건을 전달하는 것과, 회수하는 것은 별개로 봐도 상관이 없습니다.

그리고 이 문제는 Greedy한 문제가 됩니다.

트럭이 한 번 떠나게 되면, cap만큼의 물건을 배달할 수 있고, cap만큼의 물건을 회수 할 수 있다는 사실을 이해했다면,

이 문제의 절반을 풀었다고 무방합니다.

이제 배열을 거꾸로 탐색하여, 전달 한 물건이나, 회수 할 물건이 있는지 탐색을 수행합니다.

만약 존재한다면, 해당 값을 어딘가에서 감소 시켜줍니다.

그리고, 전달 할 물건이나 회수 할 물건이 존재하였기에, cap만큼의 배달량, cap만큼의 회수량을 처리 할 수 있다고,

이 값을 증가 시켜줍니다.

만약 한 번 해당 장소에 방문 한 것으로, 커버가 되지 않는다면, 다시 방문하여, cap만큼의 배달량, 회수량을 증가 시켜줍니다.

그 대신에 answer에 추가 할 때는 반복 횟수 만큼 곱해주어야 합니다.

여기서 중요합니다.

cap만큼의 배달량, 회수량을 그대로 사용하여, 다음 값을 계산할 때 그대로 이용합니다.

deliveries[i]가 2, pickups[i]가 3 이고 cap이 3이라고 하면, pickups의 값은 1만큼의 잉여 회수량이 남게 됩니다.

배열을 거꾸로 탐색한다는 의미는, i번째까지 이미 도달하고, 다시 물류창고로 돌아간다는 왕복운동의 기준으로 고려한다는 의미입니다.

이 때 잉여량이 발생하였다면, 어차피 이전 장소에서 한 번 더 사용하면 효율성 높게 업무를 처리 할 수 있게 됩니다.

여기서 주의할 점은, deliveries[i]와 pickups[i]를 가감해도 배달량과 회수량이 남아있다고 하면,

answer에 답을 추가 할 필요가 없습니다. 잉여량이 현재 배달량과 회수량을 커버하므로, 이 경우는 답을 추가하는 실수를 저지르지 맙시다.

설명을 쓰고도 제가 무슨 소리를 하는지 모르는 상황이 되었습니다.

그래도 이 문제를 깊게 고민하였다면, 약간의 도움이 됬으리라고 생각합니다.

감사합니다.

작성중인 코드―solution.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(cap, n, deliveries, pickups):
    answer = 0

    d = 0
    p = 0

    for i in range(n-1, -1, -1):

        cnt = 0

        d -= deliveries[i]
        p -= pickups[i]

        while d < 0 or p < 0:
            d += cap
            p += cap
            cnt += 1

        answer += (i + 1) * 2 * cnt

    return answer

이렇게 쉽게 풀수있는걸 너무 어렵게 풀고 있었네요 시간초과 문제 나는거 바로 해결했습니다.

wnsgh1594@gmail.com―2023.02.02 15:36
솔직히 이 풀이 몇분만에 생각해내셨나요?

ken―2023.02.02 17:55
설마 진짜 이걸 생 머리로 생각해내셨나요?

hong-soohyuk―2023.02.02 17:55
당신은 천재입니까?

yein-lee―2023.02.11 23:15
이거보고 코테접었습니다

junbok97―2023.02.12 18:28
감탄했습니다

권혁림―2023.02.14 15:40
gpt 사용한건 아니시죠? 🤣 감사합니다.

munggu―2023.02.19 00:55
감사합니다. 배울점이 많은 코드네요.

younkyounghwan―2023.02.27 12:21
d, p를 가감한 다음 d, p가 0 이상이 될 때까지 cap을 더해 채우면 시간초과를 해결할 수 있네요,, 많이 배워갑니다 감사합니다.

Thon―2023.03.02 13:41
감사합니다

localuser96―2023.03.03 14:23
이게 무슨 레벨2야 미첬어

vacu9708―2023.04.01 10:24
조건문 2개 추가 ex) cnt = -p/cap + ( 1 if -p%cap else 0 ) --> while문 제거 가능

김동욱―2023.07.03 20:30
와우...

jeongjae96―2023.07.05 22:10
와 전 풀이 이해하는데도 오래 걸리는데 어떻게 생각하셨나요 그저 코테신,,,,

이민지―2023.08.08 15:50
이거 보자마자 자살했습니다 감사합니다..

장형석―2023.09.24 00:24
스고이

dhdp332―2023.10.01 13:50
감사합니다 죽고싶어요

samkimpepper―2023.10.15 11:04
와.....감사합니다....

dbdb55―2023.11.01 15:35
설명 듣고 음 맞지맞아 하다가 코드보고 지려버렸습니다... 선생님

한상훈―2023.11.16 22:28
잘 배웠습니다.

pshn123@gmail.com―2023.12.28 22:57
대 현 서

Taegyeong Lee―2024.01.12 18:36
그리디 생각은 했다만 스택 이용해서 풀다가 .. 뭔가 에러가 난거같아요.. 근데 풀이보니 스택으로 할 필요가 없었네요. 잉여에 대해서 매번 생각해주고 있었는데

안은노―2024.03.22 23:58

전현서

2023.1.31 13:47

도저히 모르겠으면 나이스한 해설 보러 오세용

작성중인 코드―solution.py

wnsgh1594@gmail.com―2023.02.02 15:36

ken―2023.02.02 17:55

hong-soohyuk―2023.02.02 17:55

yein-lee―2023.02.11 23:15

junbok97―2023.02.12 18:28

권혁림―2023.02.14 15:40

munggu―2023.02.19 00:55

younkyounghwan―2023.02.27 12:21

Thon―2023.03.02 13:41

localuser96―2023.03.03 14:23

vacu9708―2023.04.01 10:24

김동욱―2023.07.03 20:30

jeongjae96―2023.07.05 22:10

이민지―2023.08.08 15:50

장형석―2023.09.24 00:24

dhdp332―2023.10.01 13:50

samkimpepper―2023.10.15 11:04

dbdb55―2023.11.01 15:35

한상훈―2023.11.16 22:28

pshn123@gmail.com―2023.12.28 22:57

Taegyeong Lee―2024.01.12 18:36

안은노―2024.03.22 23:58

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.