본문 바로가기
Algorithm(CodeTree, Python)/완전탐색1

[코드트리 구간 단위로 완전탐색] 바구니 안의 사탕 2 python

by kurooru 2022. 12. 8.

문제에서 말하는게 너무 애매하다.
1. 바구니가 여러 개 들어갈 수 있다는 것이 동일선상의 여러 개 중 가장 큰 하나를 선택해야 한다는 것인지, 하나의 바구니로 합쳐진다는 것인지 알 수 없었다.
2. 앞 뒤 시작점이 모두 범위 내에 들어야 하는지 아닌지 명확하지 않다.

# n, k 입력
n, k = map(int, input().split())
# linear
linear = [0] * 401
# candy, pos 입력
for _ in range(n):
    candy, pos = map(int, input().split())
    # linear에 추가
    linear[pos] += candy

# 함수들
# in_range(s, e)
def in_range(s, e):
    # s가 양수이고, e가 400 이하면 통과
    return s > 0 and e <= 400

# calc(j)
def calc(j):
    # curr_candy
    curr_candy = 0

    # 현재 범위 내에서
    for i in range(j-k, j+k+1):
        # curr_candy 구하기
        curr_candy += linear[i]
    
    # 구한 candy 갯수 반환
    return curr_candy

# 설계
# max_candy
max_candy = 0

# 완전 탐색 시작
for i in range(1, 401):
    # 양 끝점이 범위 내에 있으면,
    if in_range(i-k, i+k):
        # max_candy 업데이트
        max_candy = max(max_candy, calc(i))

# 출력
print(max_candy)