[백준 10025] 게으른 백곰 (Python)

www.acmicpc.net/problem/10025

10025번: 게으른 백곰

 

문제풀이

N, K, arr : 입력값

left, right : 양동이가 위치한 가장 좌측과 우측

start, end : 투 포인터

now : 현재 얼음의 양

 

양동이의 가장 좌측과 우측을 미리 구하여 해당 범위 안에서 투 포인터(Two-Pointer)를 통해 얼음의 최대 양을 구하는 방식으로 해결하였다.

 

1. 입력을 받으면서 양동이의 가장 좌측과 우측(left, right)을 구한다.

 

2. 투 포인터를 통해 얼음의 양을 갱신한다.

- 특정 좌표 x 에서 x - k 부터 x + k 까지의 범위를 확인해야 하므로 end 와 start 차이가 K * 2 이하일때까지 end를 증가

- 얼음의 양 갱신 후 now에서 좌측 포인터의 원소 값(arr[start])을 빼준다.

 

코드

import sys

if __name__ == '__main__':
    N, K = map(int, sys.stdin.readline().split())
    arr = [0] * 1000001
    left, right = sys.maxsize, 0

    # 입력을 받으면서 양동이의 가장 좌측과 우측 구하기
    for i in range(N):
        g, x = map(int, sys.stdin.readline().split())
        right = max(x, right)
        left = min(x, left)
        arr[x] = g

    end = left
    now, ans = 0, 0

    for start in range(left, right + 1):
        # 특정 좌표 x 에서 x - k 부터 x + k 까지의 범위를 확인해야 하므로 end 와 start 차이가 K * 2 이하일때까지 end를 증가
        while end < right + 1 and end - start <= K * 2:
            if not arr[end]:
                end += 1
                continue
            now += arr[end]
            end += 1
        ans = max(ans, now)
        now -= arr[start]
        if end >= right: break
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!