[C] 31776번: 예비 소집 결과 보고서

문제#

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

PPC 본 대회 하루 전에는 참가 팀들의 환경 적응을 위한 예비 소집이 진행된다. 예비 소집에는 3문제가 사용되었으며, N팀이 참여하였다. 각 문제와 팀에는 1번부터 차례대로 번호가 붙어 있다. PPC 운영진들은 예비 소집이 얼마나 효과적이었는지 알아보기 위해 보고서를 작성해 보기로 했다.

예비 소집의 효과를 알아내기 위해서는 성실하게 참여한 팀의 수를 구해야 한다. 예비 소집에 성실하게 참여한 팀이란 다음과 같은 조건을 만족하는 팀이다.

• 세 문제 중 최소 하나를 해결하였다.
• 문제를 번호가 작은 것부터 해결하였다. 즉, 어떤 문제를 시간 $T$에 해결했을 때 그보다 번호가 작은 문제들은 모두 해결하였으며 해결 시간이 $T$ 이하이고, 그보다 번호가 큰 문제들은 해결하지 않았거나 해결 시간이 $T$ 이상이어야 한다.

각 팀이 각 문제를 해결한 시간이 주어질 때, 예비 소집에 성실하게 참여한 팀의 수를 구하여라.

입력#

첫 번째 줄에 예비 소집에 참여한 팀의 수 $N$이 주어진다. $(1\le N\le 100)$

두 번째 줄부터 $N$개의 줄에 걸쳐 각각 $i$번 팀이 $1$번 문제, $2$번 문제, $3$번 문제를 해결한 시간을 의미하는 $3$개의 정수 $T_{i,1}, T_{i,2}, T_{i,3}$이 공백으로 구분되어 주어진다. 만약 $i$번 팀이 $j$번 문제를 해결하지 않았다면 $T_{i,j} = -1$이다. $(-1\le T_{i,j}\le 120)$

출력#

예비 소집에 성실하게 참여한 팀의 수를 출력한다.

풀이#

성실하게 참여한 팀의 조건을 3문제 기준으로 정리하면 다음과 같습니다.

1. 최소 한 문제는 풀어야 하므로 1번 문제는 반드시 풀어야 합니다.
2. 2번 문제를 풀었다면 1번 문제도 풀었고, 시간은 1번 ≤ 2번이어야 합니다.
3. 3번 문제를 풀었다면 1번, 2번도 모두 풀었고, 시간은 1번 ≤ 2번 ≤ 3번이어야 합니다.
4. 중간 문제를 건너뛰고 풀면 안 되므로, 2번을 안 풀었는데 3번만 푼 경우는 성실한 참여가 아닙니다.

즉 가능한 경우는 다음 셋뿐입니다.

• 1번만 풂
• 1번, 2번을 순서대로 풂
• 1번, 2번, 3번을 순서대로 풂

각 팀마다 위 조건을 검사해서 성실한 팀이면 개수를 1 증가시키면 됩니다.

코드#

1
#include <stdio.h>
2

3
int main() {
4
    int n;
5
    int answer = 0;
6

7
    scanf("%d", &n);
8

9
    for (int i = 0; i < n; i++) {
10
        int t1, t2, t3;
11
        scanf("%d %d %d", &t1, &t2, &t3);
12

13
        int good = 1;
14

15
        // 최소 한 문제 해결해야 하므로 1번은 반드시 풀어야 함
16
        if (t1 == -1) {
17
            good = 0;
18
        }
19

20
        // 2번을 풀었다면 1번보다 빠를 수 없음
21
        if (t2 != -1 && t1 > t2) {
22
            good = 0;
23
        }
24

25
        // 2번을 안 풀었는데 3번을 푼 경우 불가능
26
        if (t2 == -1 && t3 != -1) {
27
            good = 0;
28
        }
29

30
        // 3번을 풀었다면 2번보다 빠를 수 없음
31
        if (t3 != -1 && t2 > t3) {
32
            good = 0;
33
        }
34

35
        if (good) {
36
            answer++;
37
        }
38
    }
39

40
    printf("%d\n", answer);
41
    return 0;
42
}