문제 링크
문제
티어: 골드 3
알고리즘: 그리디
대회를 열기 위해서는 굉장히 많은 요소들을 고려해야한다. 그리고 현정이는 어떤 의미로나 좋지 못한 대회를 만드는 것으로 유명하다. 문제 부분에 관해서도, 좋은 대회라고 생각되는 기준을 한 번도 만족해본 적이 없다. 현정이가 만들고 싶은 좋은 대회란 다음 세가지 조건을 모두 만족하는 대회를 말한다.
- 모든 참가자가 한 문제 이상을 풀어야 한다.
- 모든 문제는 한 명 이상의 참가자에게 풀려야 한다.
- 모든 문제를 푼 참가자는 없어야 한다.
이런저런 경험을 겪으며 현정이는 이번에야말로 좋은 대회를 만들어내기 위해 모든 것을 바쳤다. 하지만 너무 많은 것을 바쳤는지 대회가 끝나기 전에 쓰러져버렸다. 눈을 뜬 현정이는 가장 먼저 대회 결과를 보고 이번 대회가 좋은 대회였는지를 알고싶어했다.
서둘러 대회 홈페이지에 접속한 현정이는 대회 결과를 나타내는 스코어보드를 찾아냈다. 하지만 현정이의 노트북은 모니터의 오른쪽 상단이 삼각형 모양으로 깨져있어 전체 스코어보드의 모습을 보지 못했다.
스코어보드는 더 많은 문제를 맞춘 참가자가 더 순위가 높고, 1등이 가장 위에 위치해 순위대로 정렬되어있는 형태다. 현정이의 모니터는 ◥ 모양으로 깨져있기 때문에 볼 수 있는 스코어보드의 형태는 아래 규칙을 모두 만족한다.
- i 등 참가자의 x 번 문제 결과를 볼 수 있다면 (i+1) ~ N등 참가자의 x번 문제 결과 역시 볼 수 있다.
- i 등 참가자의 x 번 문제 결과를 볼 수 없다면, 1 ~ (i-1) 등 참가자의 x번 문제 결과 역시 볼 수 없다.
- i 등 참가자의 x 번 문제 결과를 볼 수 있다면, 1 ~ x 번 문제 결과 역시 볼 수 있다.
- i 등 참가자의 x 번 문제 결과를 볼 수 없다면, x ~ M 번 문제 결과 역시 볼 수 없다.
현정이가 알 수 있는 것은 각 참가자들이 몇 문제를 풀었는지와 어떤 문제를 풀었는지에 대한 부분적인 정보이다. 현정이는 머릿속에서 행복회로를 가동하기 시작했다. 모니터가 깨져 볼 수 없는 부분을 자신이 원하는대로 채워 이 대회가 좋은대회였을 것이라고 믿는 것이다. 물론 각 참가자들이 맞춘 문제수와 볼 수 있는 결과들이 변경될 수는 없다. 깨어진 모니터에 보이는 스코어보드 정보가 주어졌을 때, 이 대회가 좋은 대회가 될 수 있는지를 알아보자.
입력
첫 줄에 이번 대회의 참가자의 수 N(1 ≤ N ≤ 100)과 문제의 수 M(1 ≤ M ≤ 10)이 주어진다. 다음 N 개의 줄에는 1등부터 N 등까지, i 등 참가자의 맞춘 문제 수 Ki (0 ≤ Ki ≤ M)와 해당 참가자의 1 ~ M번 문제에 대한 결과가 M 개가 주어진다. 결과는 맞았다면 1, 틀렸다면 0, 찢어져 결과를 알 수 없다면 -1로 주어진다.
출력
좋은대회가 될 수 있다면 “YES”, 아니라면 “NO”를 출력한다.
풀이
좋은 대회란 다음과 같다.
- 모든 참가자가 한 문제 이상을 풀어야 한다.
- 모든 문제는 한 명 이상의 참가자에게 풀려야 한다.
- 모든 문제를 푼 참가자는 없어야 한다.
입력에서 참가자 푼 문제 수가 0이거나 M이면 좋은 대회가 될 수 없다. 그래서 "NO"를 출력한다.
그 외에는 1번, 3번을 만족하기 때문에 마지막 2번 조건을 만족할 수 있는 체크해야 한다.
입력 범위를 보면 참가자 수는 최대 100이고 문제 수는 최대 10이다. 그래서 한 문제당 모든 참가자를 탐색해도 전혀 문제 될 게 없다.
그러면 M 문제를 차례대로 체크해 본다.
문제를 푼 참가자가 있다면 (1이면) 다음 문제로 넘어간다. 왜냐하면 문제는 한 명 이상만 풀면 되기 때문에 최선의 선택은 아무도 안 풀었을 때만 한 참가자가 풀게끔 해야 한다.
그래서 모든 문제를 풀 수 있다면 "YES"를 그렇지 않다면 "NO"를 출력해 주면 된다.
소스코드
import java.io.*;
import java.util.*;
public class Main {
static int N,M;
static int[][] board;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new int[N][M + 2]; //M은 총 푼 문제, M + 1은 현재 푼 문제
for(int i=0; i<N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
int cout = 0;
for(int j=0; j<M + 1; j++) {
if(j == 0) {
board[i][M] = Integer.parseInt(st2.nextToken());
} else {
int v = Integer.parseInt(st2.nextToken());
if(v == 1) {
cout += 1;
}
board[i][j - 1] = v;
}
}
board[i][M + 1] = cout;
}
if(!isPosible()) {
System.out.println("NO");
} else {
if(checkSec()) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
static boolean isPosible() {
for(int i=0; i<N; i++) {
if(board[i][M] == 0 || board[i][M] == M) {
return false;
}
}
return true;
}
static boolean checkSec() {
//두 번째 조건 확인 모든 문제는 한 명 이상의 참가자에게 풀려야 한다.
for(int i=0; i<M; i++) {
if(!checkSolved(i)) {
if(!note(i)) {
return false;
}
}
}
return true;
}
static boolean checkSolved(int ind) {
for(int i=0; i<N; i++) {
if(board[i][ind] == 1) {
return true;
}
}
return false;
}
static boolean note(int ind) {
for(int i=0; i<N; i++) {
if(board[i][ind] == -1 && board[i][M] > board[i][M + 1]) {
board[i][M + 1] += 1;
return true;
}
}
return false;
}
}time: 00:30
