[Python] 백준 20181 꿈틀꿈틀 호석 애벌레

 

20181번: 꿈틀꿈틀 호석 애벌레 - 효율성

 

1. 접근 방법

 주어진 배열에 대해 연속된 구간 중 특정 값을 넘지 않는 최소 크기를 만족하는 구간을 최대한 많이 구해야 하는 문제이다. 그러한 모든 구간을 구하는 것과 동시에 정답을 같이 구하는 과정은 간단하지는 않았다. 아마 조금 더 난이도 높은 문제에서는 동시에 처리하는 방법 등을 요구할 수 있겠지만, 이 문제는 문제에서 요구하는 구간을 찾는 과정, 정답을 찾는 과정을 따로 실행해도 가능하다.

 그래서 투포인터를 활용하여 문제에서 요구한 구간을 찾고, DP를 활용하여 정답을 구했다.

---

2. 풀이 코드

🖥python 코드 링크

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

📕코드 해설

if __name__ == "__main__":
    N, K = MIIS()
    feeds = list(MIIS()) + [0]
    feeds_status = [[0, 0] for _ in range(N)]
    left = right = 0
    feed_sum = feeds[0]
    while right < N:
        if feed_sum >= K:
            feeds_status[left] = [right, feed_sum]
            feed_sum -= feeds[left]
            left += 1
            if right < left:
                right = left
                feed_sum += feeds[right]
        else:
            right += 1
            feed_sum += feeds[right]
    dp = [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        if feeds_status == [0, 0]:
            continue
        idx, s = feeds_status[i]
        dp[i] = max(dp[i + 1], dp[idx + 1] + s - K)
    print(dp[0])

 위의 while문에서 투 포인터를 활용한 구간들을 찾는 부분이고, 아래 for문은 DP를 활용하여 정답을 구하는 부분이다. 우선 투 포인터를 사용한 부분부터 설명하면 다음과 같다.

 

 다음과 같이 문제에서 주어진 배열에 추가적으로 left, right를 0번 인덱스로, 구간의 합을 누적할 sum 값을 생성했고, 각 구간 탐색에 활용하기 위해 특정 위치에서 시작했을 때 구간의 끝 인덱스와 구간의 합을 저장할 리스트를 생성했다.

 탐색 전략은 다음과 같다.

1. left, right 두 인덱스 범위의 합을 확인한다.

2. 만약 범위의 합이 최소 만족도보다 작으면 right를 오른쪽으로 이동하고, 구간합에 누적한다.

3. 만약 범위 합이 최소 만족도 이상이면,

3-1. 구간 탐색을 저장하는 리스트에 구간의 끝인 right, 구간의 합인 sum을 저장하고,

3-2. left를 하나 오른쪽으로 이동하며, 해당 위치의 값을 구간 합에서 빼준다.

 위의 전략을 적용하면 다음과 같이 실행된다.

 먼저 right를 이동, 누적합을 확인하고 누적합이 최소 만족도를 넘는다면 기록을 하는 방식으로 진행된다.

 최종적으로 위와 같은 형태가 되고, 더 이상 탐색하지 못하는 구간은 0으로 입력해둔다.

 다음 정답을 구하기 위한 DP를 구성할 때는 인덱스를 거꾸로 탐색한다. 그렇게 활용하기 위해 구간의 끝을 같이 저장했다. 그리고 각 위치마다 이전 위치에서의 최댓값과 새로운 구간을 선택했을 때의 값 중 최댓값으로 갱신한다.

---

3. 생각 정리

 투포인터를 활용하여 구간합을 구하는 등의 과정은 어렵지 않게 적용했지만, 이를 활용하여 DP에 적용하는 과정은 고민의 시간이 조금 필요했다. 이 둘을 더 압축시켜서 활용하는 풀이도 있었지만, 거기까지 나아가지는 못했다. 투 포인터를 활용한 문제가 처음에는 간단하다고 생각했는데, 시간이 지나며 간단하게만 해결되는 것은 아니라는 생각도 든다.