[Baekjoon/C++] 1333번 - 부재중 전화

Baekjoon Online Judge

문제로 이동

 

문제

얼마전, Day Of Mourning의 새 앨범이 나왔고, 강토는 이 앨범을 들으려고 한다.

이 앨범에는 총 노래가 N곡이 들어있고, 모든 노래의 길이는 L초이다. 그리고, 노래와 노래 사이에는 5초 동안 아무 노래도 들리지 않는 조용한 구간이 있다.

강토가 앨범의 첫 곡을 듣는 순간이 0초이다. 그리고 그 0초부터 강토의 전화벨이 울리기 시작한다. 전화벨은 D초에 1번씩 울리며, 한 번 울릴 때 1초동안 울린다.

강토는 락 스피릿을 진심으로 느끼기 위해서 볼륨을 매우 크게 하고 듣기 때문에, 노래가 나오는 중에는 전화벨 소리를 듣지 못한다.

만약, 전화벨이 노래가 시작되는 순간 울린다면, 강토는 전화를 받지 못한다. 또, 전화벨이 노래가 끝나는 순간 같이 끝난다면, 강토는 전화를 받을 수 없다.

강토는 앨범을 1번만 듣는다. 즉, 모든 앨범 수록곡을 다 듣고 난 후에는 전화벨을 들을 수 있다.

강토가 전화벨을 들을 수 있는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 세 정수 N, L, D가 공백을 사이에 두고 주어진다.

 

출력

첫째 줄에 강토가 전화벨을 들을 수 있는 가장 빠른 시간을 출력한다.

 

제한

• 1 ≤ N ≤ 20
• 1 ≤ L ≤ 180
• 1 ≤ D ≤ 20

 

 

---

예제 입력	예제 출력
2 5 7	7
4 5 20	40
6 9 20	40

---

풀이

#include <iostream>
using namespace std;

int main() {
    // 총 노래가 N곡, 노래의 길이 L초, 전화벨이 울리는 간격 D초
    int N, L, D;
    cin >> N >> L >> D;

    int btime; // 전화벨이 울리는 시간
    bool isfind = false; // 전화벨을 들을 수 있는 시간을 찾았는가?

    for (int i = 1; ; i++) {
        btime = D * i;

        for (int j = 1; j <= N; j++) {
            int mtime = L * j + 5 * (j - 1); // 노래가 나오는 시간

            // 노래와 노래 사이의 조용한 구간에 btime이 포함되는지 확인
            if (btime >= mtime && btime < mtime + 5) {
                isfind = true;
                break;
            }
        }

        // 전화벨 듣는 시간을 찾았거나 앨범이 끝났을 때
        if (btime > N * L + (5 * (N - 1)) || isfind == true)
            break;
    }

    // 출력
    printf("%d\n", btime);

    return 0;
}

 

문제 풀이를 머리로만 생각하려니 헷갈리기만 했기에 주어진 예제 2개를 그림으로 표현해 풀었다.

1. 예제 1 : 음악이 2번 5초 동안 재생되고 전화벨이 7초마다 울린다.

2. 예제 2 : 음악이 4번 5초 동안 재생되고 전화벨이 20초마다 울린다.

예제 1의 그림에서는 가장 먼저 전화벨이 울리는 시간이 7 ~ 8초로 음악 없이 조용한 시간인 5 ~ 10초 사이였기에 7초에 전화벨을 들을 수 있다.

예제 2의 그림을 보면 가장 먼저 전화벨이 울리는 시간은 20 ~ 21초로 음악이 나오기 시작한 부분에서 울렸기에 전화벨을 듣지 못하고, 모든 음악이 끝난 뒤는 40 ~ 41초에서 전화벨을 듣고 전화를 받을 수 있다.

 

n * m ~ n * m + 5라는 전화벨을 들을 수 있는 범위를 구할 수 있는데, 여기서 음악이 시작되는 순간에 전화벨이 울리면 전화를 받을 수 없으므로 n * m <= 전화벨이 울리는 시간 <n * m + 5이어야 한다.

 

위의 범위를 이용해서 문제를 풀었으며, 또한 앨범이 끝났을 때를 위해 아래의 코드를 추가했다.

if (btime > N * L + (5 * (N - 1)) || isfind == true)
            break;