문득, 내가 옛날에 풀어왔던 문제는 지금 풀어보면 어떨까 생각이 들어서
내가 난이도 기여를 한 문제를 쭉 살펴보다가
내가 제일 처음 기여를 한 문제이자, 브론즈 문제치고 정말 어렵다라는 생각이 들어서 이건 실버다 싶어서 기여했던 문제. '부재중 전화' 라는 문제를 다시 풀어보았다.
그리고 어이없게 맞왜틀 시전해주고 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ (다시 바로 맞추긴 했음)
풀이를 쓰기로 결심했다.
BOJ 1333 - 부재중 전화 링크
(2022.08.31 기준 B2)
(브론즈 문제를 치팅..하진 않겠지....)
문제
노래가 0초부터 L 길이만큼 N번 나오고 그 사이에 5초간 나오지 않는다고 했을 때,
0초부터 D초마다 1초간 전화벨이 울릴 때, 노래가 나오지 않고 전화벨이 울리는 제일 빠른 시간
알고리즘
특정한 알고리즘은 없다. 그냥 구현
다만, 문제 해석을 잘 해야 한다.
풀이
문제 해석이 처음엔 어려울 수 있다.
왜냐 하면, 만약 시간을 수직선 상이라고 표현한다면, 한 점이 아닌 구간으로 생각해라고 유도하기 때문. (전화벨은 1초 간, 노래는 L초 간 울리기 때문)근데 너무 어렵게 생각하지 말자.
만약 0초부터 1초간 전화벨이 울리면
0 ≤ 전화벨 < 1 이라는 소리이다.
그러니깐 즉, 끝나는 부분은 포함하지 않는다고 생각하면 된다. (그냥 range라는 개념)예를 들어 대충 그림으로 설명하자면
빨강이 노래, 파랑이 전화벨이면, 전화벨을 들을 수 있다.그럼 이제 구현을 해야 하는데
내가 생각한 방법은 2개가 있다.
1. 노래가 하나 끝날 때마다 그 다음 쉬는 구간에 전화벨이 울리는지 확인
2. 노래가 나오는 시간대를 전처리를 하여 전화벨 울리는 간격마다 확인시간적으로는 1번이 좋은데
보기 좋게, 그리고 풀기 쉽게는 2번이 좋다.
그래서 난 2번을 풀이해보겠다.먼저 앨범의 총 노래 길이는 N * L + (N - 1) * 5 이다.
그럼 초마다 노래가 나오는지 상태를 담아 줄 배열을 만들고
L + 5 간격으로 L 길이만큼 노래가 나온다는 상태로 저장해주자.for (int i = 0; i < 앨범 총 길이; i = i + L + 5) { for (int j = i; j < i + L; j++) { 시간[j] = true } }그 다음은, 0초부터 앨범 총 길이까지 D초마다 노래가 나오는지 체크해주고 나오지 않으면 그 시간을 출력.
만약, 범위 끝까지 노래가 나왔다면, 범위 안 마지막 체크했던 시간 + D초를 출력해주면 된다.
앨범 총 길이의 시간을 넘으면 노래가 나오지 않기 때문이다.for i in range(0, 앨범 총 길이, D): if not 시간[i]: print(i) break else: print(i + D)
코드
import sys; input = sys.stdin.readline
N, L, D = map(int, input().split())
total = N * L + (N - 1) * 5 # 앨범의 총 길이
song = [False] * total # 노래가 나오는 시간대를 체크할 것임
for i in range(0, total, L + 5): # 각 노래는 0 초부터 시작해서 L + 5 초마다 나온다.
for j in range(i, i + L): # 시작하는 부분 i부터 노래가 끝나는 부분인 i + L 전까지 체크
song[j] = True
for i in range(0, total, D): # 0초부터 D초마다 노래가 나오는지 체크
if not song[i]:
print(i)
break
else:
print(i + D)여담
이 문제는 비교적 난이도는 많이 낮지만, 백준 브론즈 문제 중에선 난이도 Top 10 안에 든다고 생각이 든다. 왜냐면, 이 문제를 처음 접했을 때, 문제 해석이 생각보다 까다로웠기 때문이다.
(오죽했으면 내가 난이도 기여 실버를 줬을까..)이런 문제는 난이도와 상관 없이 맞왜틀 많이 하는 유형의 문제인데, 그래도 다행히 질문 게시판에 반례가 많이 있어서 참고하면서 풀면 수월할 것이다.
대표적으로 이 글 (반례모음집)난이도가 낮든 높든 문제를 잘 읽고 풀자!
