[Python] 24833번 Air Conditioner

https://www.acmicpc.net/problem/24833

---

 

25/09/12

 

 

이게 어떤 알고리즘인지는 잘 모르겠는데, 문제에 대한 시각화를 해보고 싶어서 글을 적게되었다.

---

 

문제 접근 방식:

 

가로축은 시간을 나타내고, 세로축은 온도를 나타낸다.

 

그리고 빨간 선은 해당 시점에 특정 손님이 원하는 온도의 범위이다.

 

시간 1당 온도를 최대 1올리거나 1내릴 수 있으므로, 회색으로 칠한 범위가 해당 시점 이후로부터 가능한 온도의 범위가 된다.

 

이 회색 범위와 빨간 선이 겹친다면 겹친 구간에서 다시 기울기가 1인 직선과 기울기가 -1인 직선을 그어서 범위를 표현할 수 있다.

 

만약 회색 범위와 빨간 선이 겹치지 않는다면 불가능 한것이고, 모든 손님에 대해서 겹치는게 가능하면 가능한 것이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 24833번 Air Conditioner
'''
문제
길동은 불고기 식당을 운영한다. 손님이 많아 미리 예약을 하는 경우가 많다.

길동은 손님들을 만족시키기 위해 각 손님이 선호하는 온도 범위를 모두 외워두었다.
예약 목록을 보며, 에어컨을 조절해 모든 손님을 만족시킬 수 있는지 알아보고자 한다.

식당의 에어컨은 다음 3가지 상태를 가진다: off, heating, cooling.

off일 때: 식당 온도는 변하지 않는다.
heating일 때: 온도는 1분에 1씩 증가한다.
cooling일 때: 온도는 1분에 1씩 감소한다.

길동은 정수 시각마다 원할 때 얼마든지 상태를 바꿀 수 있다. 초기 상태는 off이다.

각 손님은 세 값으로 특징지어진다:

t_i = i번째 손님이 식당에 도착하는 시각(분)
l_i = 선호 온도 범위의 하한
h_i = 선호 온도 범위의 상한

손님은 도착 순간의 온도가 선호 범위에 있으면 만족한다.
즉, i번째 손님은 t_i분에 식당 온도가 [l_i, h_i](양끝 포함) 안에 있을 때에만 만족한다.

초기 온도와 예약 손님들의 방문 시각·선호 온도 범위가 주어질 때, 모든 손님을 만족시킬 수 있는지 판단하라.

입력
여러 테스트 케이스가 주어진다. 첫 줄에 테스트 케이스 수 q (1≤q≤500)가 주어진다.

각 테스트 케이스에 대해:

첫 줄에 정수 n,m (1≤n≤100, -10^9≤m≤10^9)이 주어진다.
n: 예약한 손님 수, m: 식당의 초기 온도.

다음 n개의 줄의 i번째 줄에 세 정수 t_i, l_i, h_i (1 <= t_i <= 10^9, -10^9 <= l_i <= h_i <= 10^9)가 주어진다.
손님들은 도착 시각 비내림차순으로 주어지며, 현재 시각은 0이다. 선호 온도 범위는 양끝 포함이다.

출력
각 테스트 케이스마다, 모든 손님을 만족시킬 수 있으면 "YES", 불가능하면 "NO"를 출력한다.
대소문자는 아무 형태로나 출력해도 된다.
'''
import sys
input = sys.stdin.readline

def solve(test_case_num):
    N, M = map(int, input().split())
    query = list(tuple(map(int, input().split())) for _ in range(N))
    before_t = 0
    spread_upper, spread_lower = M, M
    for i in range(N):
        t, l, h = query[i]
        upper, lower = spread_upper+(t-before_t), spread_lower-(t-before_t)
        if upper < l or lower > h:
            print('NO')
            return
        spread_lower, spread_upper = max(l, lower), min(h, upper)
        before_t = t
    print('YES')
    return

def main():
    T = int(input())
    for i in range(1, T+1):
        solve(i)
    return

main()