[Python/파이썬] 백준 19951번 태상이의 훈련소 생활

19951번: 태상이의 훈련소 생활

 

문제

2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연병장(운동장)의 흙을 옮기는 일을 주고 제대로 수행하지 못하면 징계를 내리려고 한다.

연병장은 일렬로 이어진 $N$개의 칸으로 이루어져 있으며 각 칸마다 높이를 가지고 있고, 첫 번째 칸부터 순서대로 1번, 2번, 3번, ..., $N$번 칸으로 명칭이 붙어있다. 조교들은 총 $M$명이 있으며, 각 조교들은 태상이에게 $a$번 칸부터 $b$번 칸까지 높이 $k$만큼 흙을 덮거나 파내라고 지시한다. 흙은 주변 산에서 얼마든지 구할 수 있으므로 절대로 부족하지 않다.

태상이는 각 조교의 지시를 각각 수행하면, 다른 조교의 지시로 흙을 덮어둔 칸을 다시 파내기도 하는 비효율적인 일이 발생하는 것을 깨달았다. 그래서 태상이는 각 조교의 지시를 모아 연병장 각 칸의 최종 높이를 미리 구해 한 번에 일을 수행하려고 한다.

불쌍한 태상이를 위해 조교들의 지시를 모두 수행한 뒤 연병장 각 칸의 높이를 구하자.

입력

첫 줄에 연병장의 크기 $N$과 조교의 수 $M$이 주어진다.

둘째 줄에 연병장 각 칸의 높이 $H_i$가 순서대로 $N$개 주어진다.

셋째 줄부터 $M$개의 줄에 각 조교의 지시가 주어진다.

각 조교의 지시는 세 개의 정수 $a, b, k$로 이루어져 있다.

• $k ≥ 0$인 경우 $a$번 칸부터 $b$번 칸까지 높이가 각각 $|k|$ 만큼 늘어나도록 흙을 덮어야 한다.
• $k < 0$인 경우 $a$번 칸부터 $b$번 칸까지 높이가 각각 $|k|$ 만큼 줄어들도록 흙을 파내야 한다.

출력

모든 지시를 수행한 뒤 연병장 각 칸의 높이를 공백을 사이에 두고 출력한다.

제한

• $1 ≤ N ≤ 100,000$
• $1 ≤ M ≤ 100,000$
• $-10,000 ≤ H_i ≤ 10,000$
• $N, M, H_i$는 정수
• 조교의 지시
  • $1 \leq a \leq b \leq N$
  • $|k| ≤ 100$

 

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
h = list(map(int, input().split()))
cmd = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, k = map(int, input().split())
    cmd[a].append((k, True))
    cmd[b].append((k, False))

tmp = 0
for i in range(1, n+1):
    plus = 0
    minus = 0
    for c in cmd[i]:
        if c[1]:
            plus += c[0]
        else:
            minus += c[0]
    tmp += plus
    h[i-1] += tmp
    tmp -= minus

print(*h)

 

조교의 명령이 들어올 때마다 a부터 b까지 k를 더하거나 파내면 너무 비효율적이라 안된다.

그렇기 때문에 cmd라는 배열에 들어온 명령을 미리 저장해놓고 나중에 한 번의 for문만으로 계산을 하도록 할 것이다. 

시작점과 끝점은 표시를 해줘야 하기 때문에 시작점은 True, 끝점은 False로 값을 주었다. 

이렇게 모두 명령을 저장한 뒤 1~n까지 for문을 돌며 명령이 시작되는 칸, 즉 True인 칸에서는 tmp에 값을 더해주고, False인 칸에서는 tmp에서 값을 빼준다.

이때 주의할 점 2가지가 있다.

1. 위의 그림은 편의상 한 칸에 (k, T/F)가 하나씩만 저장되어 있는 것같이 보이지만 실제로는 그렇지 않기 때문에 cmd의 같은 칸에 있는 명령들은 한 번에 같이 계산해야 한다.
2. False인 칸도 거기까지는 k만큼 흙을 덮거나 파내어야 하므로 h[i-1]에 tmp 더하기 연산을 한 뒤에 minus만큼 빼주어야 한다.