BOJ 2991 - 사나운 개

문제

BOJ 2991 - 사나운 개

두 마리의 개가 각각 A분 사납고 B분 온순한 주기, C분 사납고 D분 온순한 주기를 반복할 때, 세 배달원이 도착하는 시간에 몇 마리에게 물리는지 구하라.

입력

첫째 줄에 A, B, C, D, 둘째 줄에 세 배달원의 도착 시간이 주어진다.

출력

각 배달원이 물리는 개의 수를 한 줄에 하나씩 출력한다.

예제

풀이

각 배달 시간에 대해 두 개의 주기별 모듈러 연산으로 사나운 상태인지 판별한다.

1. 첫 번째 개의 주기는 A + B이며, 시간 % (A+B)가 0 초과 A 이하이면 사나운 상태이다
2. 두 번째 개의 주기는 C + D이며, 시간 % (C+D)가 0 초과 C 이하이면 사나운 상태이다
3. 각 배달원에 대해 사나운 개의 수를 합산한다

핵심 아이디어: 주기적으로 반복되는 행동은 모듈러 연산으로 현재 시점의 상태를 O(1)에 판별할 수 있다.

코드

A, B, C, D = map(int, input().split())
delivery = list(map(int, input().split()))
 
for i in delivery:
    dog = 0
    if 0 < i % (A + B) <= A:
        dog += 1
    if 0 < i % (C + D) <= C:
        dog += 1
 
    print(dog)

복잡도

• 시간: O(M) (M: 배달원 수)
• 공간: O(M)