[백준 BOJ] 30404번 오리와 박수치는 춘배 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 그리디 알고리즘을 활용한 응용문제

백준의 30404번 문제는 그리디 알고리즘을 활용하여 해결해야 하는 문제이다.

해당 문제는, 오리가 실망하여 돌아가지 않도록 오리의 소리에 춘배가 박수를 쳐야 할 때 춘배가 박수를 쳐야 하는 횟수의 최솟값을 구하여 출력해야 하는 문제이다.

이때, 오리가 돌아가지 않도록 박수를 쳐야 하는 규칙은 아래와 같다.

• 오리는 n번(입력값) 소리를 낸다.
• 오리가 각각의 소리를 낸 시간 + k값(입력값) 안으로 최소 한 번의 박수를 쳐야 한다.

 

필자는 해당 규칙에 대해, 큐를 활용하여 문제 해결을 시도해 보았다.

다소 저렴하고 미흡할 수 있으나, 구체적인 로직은 입력 예제를 기반으로 그림을 따로 그려서 표현해 보았다.

요약하자면, 앞서 오리가 소리를 내었던 시간에 대해 박수를 칠 수 있는 시간대에 있어, 오리가 추가로 더 소리를 낸 적이 있는지를 확인해 가며 최솟값을 구해보려 하였다.

보다 자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 오리가 소리를 낸 횟수(n)와 임의의 값 k를 입력받는다.

 

2) 정답을 구하는 데에 활용할 큐 q를 미리 선언해 둔다.

 

3) n의 크기만큼, 반복문을 수행하여 오리가 소리를 낸 시간을 하나씩 입력받도록 한다.

입력을 받는 대로, 순차적으로 q에 값을 push하도록 한다.

 

4) 박수를 쳐야 하는 최솟값을 저장할 변수 count를 0으로 초기화하여 선언해 둔다.

 

5) q가 빌 때까지, 반복문을 수행하여 아래의 연산을 취한다.

- 임의의 변수 end를 선언하고, q의 front 요소에 k를 더한 값으로 변숫값을 초기화해 둔다.

(end에 저장된 값은, 한 번의 박수를 쳐야 하는 시간대의 가장 마지막 시간 값을 의미한다.)

- q의 front값을 pop한 뒤, 한 번의 박수를 카운팅 하기 위해 count에 1을 더하도록 한다. 

- 다른 반복문을 활용하여, end 시간 안에 오리가 소리를 더 내었는지를 확인하도록 한다.

해당되는 값이 q의 front에 존재한다면, 한 번의 박수로 함께 퉁치기 위해(?) pop 연산을 수행하도록 한다.

 

6) 모든 연산이 완료되었다면, 최종적으로 저장된 count의 값을 출력한 뒤 실행을 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;

//백준 30404번 코드
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    queue<int> q;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        q.push(num);
    }

    int count = 0;
    while (!q.empty()) {
        int end = q.front() + k;
        q.pop();
        count++;

        while (!q.empty() && q.front() <= end) {
            q.pop();
        }
    }

    cout << count << endl;
}

 

접근 방법

(2023.10.29 백준 30404번 문제 제출 결과)