[백준] 태상이의 훈련소 생활

변수 설명

N[] = 모래의 초기 상태

a, b deg = a이상 b이하 deg만큼 모래를 채워라(빼라) 

풀이 

a~b까지 deg를 누적해서 더해주고 b + 1에서 deg를 소멸시켜주자

누적해서 더해주는 것은 각 인덱스에 무엇을 얼만큼 더해야 하는지 알려주기 때문에 누적하는 것이 굉장히 중요하다.

여기서 문제점은 a ~ b까지 deg를 누적해서 더했다면 n[b + 1] = [b] + b[n + 1]이 된다. 

n[b + 1]에서는 deg값을 인덱스마다 누적 할 필요가 없는데 어떻게 하면 소멸할 수 있을까를 고민하면 된다.

b[n + 1]에 -deg 값을 넣음으로써 해당하는 누적 값을 없앨 수 있다. 

풀이 

def make_psum(arr):

    psum = []
    psum.append(arr[0])

    for i in range(1, len(arr)):
        psum.append(psum[i - 1] + arr[i])

    return psum


def solution(board, order_by_superior):
    record_board = [0] * len(board)


    for s, e, d in order_by_superior:
        record_board[s - 1] += d

        if e != len(board):
            record_board[e] += -d

    result_psum = make_psum(record_board)
    answer = [x + y for x, y in zip(board,result_psum)]

    return answer

if __name__ == "__main__":
    n, m = map(int, input().split())
    board = list(map(int, input().split()))

    order_by_superior = []

    for _ in range(m):
        order_by_superior.append(list(map(int, input().split())))

    answer = solution(board, order_by_superior)

    for i in answer:
        print(i, end=" ")

# 10 3
# 1 2 3 4 5 -1 -2 -3 -4 -5
# 1 5 -3
# 6 10 5
# 2 7 2

문제

백준 링크

소감

누적합 문제인지는 바로 느낌이 왔다. m 값을 보고 작업 방식을 보니 누적합이라고 생각이 들었다.

첫 번째 생각은 균일하게 더해지니깐 초기 n 값을 누적합으로 주고, (b -a + 1) * k 를 해서 빼자 라는 생각이 들었다. 

해당 방법을 타겟으로 잡고 접근하니 n의 값이 다른데 누적합을 적용하는 것은 옳지 못하다고 생각이 들었기에 위의 방식으로 변경했다.