[자바] 백준 18248 - 제야의 종 (java)

 문제 : boj18248

---

 

필요 알고리즘 개념

• 정렬, 그리디
  
  • 그리디라고 봐야할진 잘 모르겠다. 아무튼 규칙을 찾아 정렬해서 해결할 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  문제를 이해하기 상당히 어려운 문제였던 것 같다. 결국 중요한건 N명의 사람이 종에서 특정 거리만큼 떨어져 있고, 그 위치가 바뀌지 않는다('타종이 진행되는 동안 사람들은 종소리에 집중하기 위해 움직이지 않는다')는 점이다.

 

  그렇다면 이 문제에서 묻는 '불가능한 상황'은 '종에서 더 가까운 사람이 못들었는데, 종에서 더 먼 사람이 들은적이 있냐' 라고 생각해볼 수 있다. 그럼 이제 누가 더 종과 가까운지 알면 된다. R이 계속 바뀌더라도 어쨌든 종에서 R 이내에 있는 모든 사람이 듣는다고 한다. 따라서 단순하게 생각해보면 M번의 타종에 대해 더 많이 들은 사람이 더 거리가 가깝다고 생각해볼 수 있다. 따라서 로직은 아래와 같이 세워볼 수 있다.

 

1. N명의 사람을 M번의 타종에서 더 많이 소리를 들은 사람 순서대로 정렬한다.

@Override
public int compareTo(Node o) {
    return o.sum - this.sum;
}

 

2. M번의 타종 각각에 대해, 더 가까운 사람이 종 소리를 못들었는데 더 먼 사람이 종 소리를 들은 경우가 있다면 NO를 출력한다. 모든 M번의 타종에 대해 그런 경우가 없다면 YES를 출력한다.

for (int i = 0; i < m; i++) {
    int bf = arr[0].hear[i];
    for (int j = 1; j < n; j++) {
        if (bf == 0 && arr[j].hear[i] == 1) {
            System.out.println("NO");
            return;
        }
        bf = arr[j].hear[i];
    }
}
System.out.println("YES");

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Node implements Comparable<Node> {
    int[] hear;
    int sum = 0;

    public Node(int m, String str) {
        StringTokenizer st = new StringTokenizer(str);
        hear = new int[m];
        for (int i = 0; i < m; i++) {
            int cur = Integer.parseInt(st.nextToken());
            sum += cur;
            hear[i] = cur;
        }
    }

    @Override
    public int compareTo(Node o) {
        return o.sum - this.sum;
    }
}

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Node[] arr = new Node[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new Node(m, br.readLine());
        }
        Arrays.sort(arr);

        for (int i = 0; i < m; i++) {
            int bf = arr[0].hear[i];
            for (int j = 1; j < n; j++) {
                if (bf == 0 && arr[j].hear[i] == 1) {
                    System.out.println("NO");
                    return;
                }
                bf = arr[j].hear[i];
            }
        }
        System.out.println("YES");
    }
}