[Python] 백준 : 질문은 계속돼 32194, 누적합, prefix

 

 

📝 문제

닝닝이는 예, 아니오로 답할 수 있는 질문을 좋아한다. 닝닝이 한 첫 번째 질문의 답은 "예"였다.

이후, 2번째부터 닝닝이는 다음과 같은 형태의 질문을 계속해서 할 것이다.

• 1 x y : x 번째 질문부터 y 번째 질문의 답이 모두 "예"였습니까?
• 2 x y : x 번째 질문부터 y 번째 질문의 답이 모두 "아니오"였습니까?

닝닝이가 위 질문을 하는 시점에, 당신은 이미 닝닝이가 한 x 번째 질문부터 y 번째 질문에 답한 적이 있다. 닝닝이가 하는 질문에 모두 답하는 프로그램을 작성하시오.

 

첫째 줄에, 닝닝이가 한 첫 번째 질문을 제외한 질문의 개수 N 이 주어진다. 즉, 닝닝이는 총 N 개의 질문을 했다.

이후 N 개의 줄에, 닝닝이가 한 각 질문이 차례대로 1 x y 또는 2 x y의 형태로 주어진다.

 N 개의 줄에 걸쳐, 닝닝이가 한 질문의 답을 순서대로 출력한다. 각각의 답이 "예"라면 Yes 를, "아니오"라면 No 를 출력한다.

 

🫠 나의 풀이 (시간 초과)

import sys
sys.stdin = open('input.txt', 'r')
# input = sys.stdin.readline

N = int(input())
lst = [1]

for _ in range(N):
    q, x, y = map(int, input().split())

    if q == 1:
        if 0 in lst[x - 1:y]:
            print('No')
            lst.append(0)
        else:
            print('Yes')
            lst.append(1)
    else:
        if 1 in lst[x - 1:y]:
            print('No')
            lst.append(0)
        else:
            print('Yes')
            lst.append(1)

 

🧞‍♂️ 다른 사람의 풀이

# input
6
1 1 1
2 1 2
2 2 3
1 1 2
2 3 4
1 5 5

# output
Yes
No
No
Yes
Yes
Yes

import sys
sys.stdin = open('input.txt', 'r')
# input = sys.stdin.readline

N = int(input())
lst = [1] # 각 질문의 답 저장 Yes = 1, No = 0
prefix = [0, 1] # 누적합: prefix[i]는 lst[0:i]의 1의 개수를 의미

for _ in range(N):
    q, x, y = map(int, input().split())

    if q == 1: # 구간 [x-1, y+1)의 답이 Yes 인가?
        cnt = prefix[y] - prefix[x - 1]

        if cnt < (y - x + 1): # 구간 내 0이 있음
            print('No')
            lst.append(0)
        else: # 구간에 0이 없음
            print('Yes')
            lst.append(1)
    else: # 구간 [x-1, y+1)의 답이 No 인가?
        cnt = prefix[y] - prefix[x - 1]

        if cnt > 0: # 구간 내 1이 있음
            print('No')
            lst.append(0)
        else: # 구간에 1이 없음
            print('Yes')
            lst.append(1)

    prefix.append(prefix[-1] + lst[-1])
    
# lst = [1, 1, 0, 0, 1, 1, 1]
# prefix = [0, 1, 2, 2, 2, 3, 4, 5]

 

 

 

🔗 https://www.acmicpc.net/problem/32194