| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 94 | 41 | 38 | 52.055% |
서울과학고 매점에 드디어 두쫀쿠가 입고되었습니다! 매점 아저씨는 이 사실을 알리기 위해, 매점을 방문하는 $N$명의 학생에게 하루 동안 두쫀쿠 무료 나눔 이벤트를 하려고 합니다. 매점에서 고용할 수 있는 영업 사원은 총 $M$명 있으며, 각 영업 사원의 고용 여부는 자유롭게 정할 수 있습니다. $i$번째 영업 사원을 고용하면 $p_i$번째 학생부터 $q_i$번째 학생까지 각 학생마다 두쫀쿠를 $r_i$개씩 나누어 줍니다.
서울과학고 학생들은 두쫀쿠를 두 개씩 겹쳐 먹기 때문에, 홀수 개의 두쫀쿠를 나눠준다면 두쫀쿠 한 개를 더 구매하기 위해 매점에 다시 들를 것입니다. 매점 아저씨는 이 사실을 알고 $1$번 학생부터 $N$번 학생까지 모든 학생에게 홀수 개의 두쫀쿠를 나누어주려고 합니다. 매점 아저씨의 원대한 목표를 이루기 위해 매점에서 무료 나눔에 사용해야 하는 두쫀쿠의 총 개수의 최솟값을 계산하는 프로그램을 작성하세요.
첫째 줄에 양의 정수 $N$과 $M$이 공백으로 구분되어 주어집니다.
둘째 줄부터 $M$개의 줄에 걸쳐 영업 사원들의 정보가 주어집니다. $i+1$번째 줄에 정수 $p_i$, $q_i$, $r_i$가 공백으로 구분되어 주어집니다.
첫째 줄에 매점에서 무료 나눔에 사용해야 하는 두쫀쿠의 총 개수의 최솟값을 출력합니다. 만약 모든 학생에게 홀수 개의 두쫀쿠를 나눠줄 수 없다면 Dujjonku so expensive T.T를 출력합니다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 9 | $N \le 4$ |
| 2 | 7 | 모든 $1 \leq i \leq M$에 대해 $p_i = q_i$ |
| 3 | 8 | $p_1 < q_1 < p_2 < q_2 < \cdots < p_M < q_M$ |
| 4 | 28 | $p_i < p_j \le q_i < q_j$를 만족하는 정수 $(i, j)$ 순서쌍이 존재하지 않습니다. ($1 \leq i, j \leq M$) |
| 5 | 48 | 추가 제한 조건이 없습니다. |
6 5 1 3 3 2 4 10 3 5 5 4 6 1 1 6 5
12
3 4 1 1 5 2 2 4 3 3 2 3 3 1
Dujjonku so expensive T.T
School > 서울과학고등학교 > 2026 SciCom Qualification Test D번