"백준 18248번: 제야의 종" 문제를 풀어봤어요!

🤔 문제 설명

제야의 종 타종은 한 해의 끝과 새로운 한 해의 시작을 알리는 행사이다. 이 행사에서는 보신각의 종을 여러 번 타종한다.

제야의 종을 타종해서 나는 종소리는 종으로부터 특정 거리 R 이내에 있는 사람은 모두 들을 수 있고, R보다 멀리 떨어져 있는 사람은 모두 들을 수 없는 특징을 가지고 있다. 여러 명의 정치인, 연예인 등의 유명 인사가 돌아가며 타종하기 때문에 매번 종을 칠 때마다 R의 값은 바뀐다.

N명의 사람이 있고, 2019년 12월 31일(TMI: 출제자의 생일임) 밤에 이루어진 제야의 종 타종에서는 총 M번 종을 쳤다고 하자. M번의 타종이 진행되는 동안 사람들은 종소리에 집중하기 위해 움직이지 않는다.

N명의 사람 각각이 각 M번의 타종을 들었는지의 여부가 주어졌을 때, 실제로 가능한 상황인지 판별하여라.

---

✅ 나의 풀이

⛰️ 실패작1

" 앞에 있는 사람이 못들었는데 뒤에 있는 사람이 들을 수가 없다. "라는 생각을 가지고 입력값을 받아서 앞뒤가 0,1인지를 판단해서 문제를 해결해 보았다.

#include <iostream>
using namespace std;

/*
백준 18248번: 제야의 종
*/

int main() {
    int N, M;
    cin >> N >> M;

    int** arr = new int*[N];
    for(int i=0; i<N; i++) {
        arr[i] = new int[M];
    }

    for(int i=0; i<N; i++) {
        for(int j=0;j<M;j++) {
            cin >> arr[i][j];
        }
    }

    int ch = 1;

    for(int i=0; i<N-1; i++) {
        if(N == 1) break;
        for(int j=0;j<M;j++) {
            if(arr[i][j] < arr[i+1][j]) {
                ch = 0;
                break;
            }
        }
        if(ch == 0) break;
    }

    if(ch == 1) cout << "YES\n";
    else cout << "NO\n";	    
}

➡️ 실패!

⛰️ 실패작2

실패작1에서는 단순히 앞뒤로 계속 비교했다면 이번에는 1번째 종에 대해서 첫번째 사람을 기준으로 잡고 행을 더하면서 첫번째 사람과 뒤에 사람들을 일일히 비교했다.

#include <iostream>
using namespace std;

/*
백준 18248번: 제야의 종
*/

int main() {
    int N, M;
    cin >> N >> M;

    int** arr = new int*[N];
    for(int i=0; i<N; i++) {
        arr[i] = new int[M+1];
    }

    for(int i=0; i<N; i++) {
        for(int j=0;j<M;j++) {
            cin >> arr[i][j];
        }
    }

    bool answer = true;

    for(int i=0;i<M;i++) {
        int check = arr[0][i];
        for(int j=0;j<N;j++) {
            if(check < arr[j][i]) {
                answer = false;
                break;
            }
            check = arr[j][i];
        }
    }

    if(answer) cout << "YES\n";
    else cout << "NO\n";
   
}

➡️ 실패!

😂 성공!

일일히 종이에 그림으로 그려가면서 해본 결과, 각 행(사람)마다 종을 들은 횟수를 따로 저장해서 들은 횟수가 많은 사람일수록 종에 가까이 있다는 것을 깨달았다. 정렬이 필요하다!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
백준 18248번: 제야의 종
*/


int main() {
    int N, M;
    cin >> N >> M;

    vector <vector<int>> arr(N, vector<int>(M+1,0)); // N행 M열을 가지는 벡터 선언

    for(int i=0; i<N; i++) {
        int sum =0;
        for(int j=0;j<M;j++) {
            cin >> arr[i][j];
            sum += arr[i][j];
        }
        arr[i][M] = sum;
    }

    bool answer = true;

    sort(arr.begin(), arr.end(), [M](const vector<int>& v1, const vector<int>& v2){
        return v1[M] > v2[M];
    });

    for(int i=0;i<M;i++) {
        int check = arr[0][i];
        for(int j=0;j<N;j++) {
            if(check < arr[j][i]) {
                answer = false;
                break;
            }
            check = arr[j][i];
        }
    }

    if(answer) cout << "YES\n";
    else cout << "NO\n";
   
}

2차원 배열을 정렬하기 위해서는 일반적인 sort를 쓸수 없다는 것을 깨닫고 vector로 다시 만들어서 성공했다. vector에 대해서 자세히 정리해야겠다.