19618번 - 벽 칠하기 서브태스크다국어언어 제한함수 구현
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 512 MB | 203 | 52 | 45 | 24.457% |
문제
성렬이는 자기가 사는 집의 벽을 칠한지 한참 되었기 때문에 다시 칠하려고 한다. 벽은 N개의 구간으로 되어 있는데, 0부터 N − 1까지 번호가 매겨져 있다. 이 문제에서, K 가지 다른 색깔이 있고 이 색을 각각 0 이상 K − 1 이하인 정수로 표현하자 (예를 들면, 붉은 색은 0, 파란 색은 1, 등등 같은 식으로) 성렬이는 벽의 i 번째 구간을 색깔 C[i]로 칠하려고 한다.
성렬이는 벽 칠해주는 회사에 이 일을 맡기기로 했는데, 이 회사에는 M 명의 일꾼이 있고 각 일꾼은 0 부터 M − 1 까지 번호가 매겨져 있다. 불행히도, 일꾼들은 자기가 좋아하는 색만 칠하려고 한다. 구체적으로는, j 번 일꾼은 A[j] 개의 색을 좋아하고, 색 B[j][0], 색 B[j][1], …, 색 B[j][A[j] − 1] 중 하나로만 구간을 칠한다.
성렬이는 벽 칠해주는 회사에 여러 번 지령을 보낼 수 있다. 성렬이가 회사에 보내는 지령 하나는 두 파라미터 x와 y로 이루어지는데, 0 ≤ x < M이고 0 ≤ y ≤ N − M이다. 모든 0 ≤ l < M에 대해서 회사는 ((x + l) mod M)번 일꾼 에게 (y + l) 번째 구간을 칠하게 시킨다. 만약 어떤 l 값에서 ((x + l) mod M)번 일꾼이 색 C[y + l]을 좋아하지 않는 경우가 있다면, 이 지령은 무효가 된다.
성렬이는 지령 하나를 보낼 때마다 돈을 내야 하기 때문에, 가능하다면 벽의 모든 구간을 원하는 색깔로 칠하는 명령의 최소 횟수, 또는 원하는 색깔로 벽을 칠할 수 없다는 것을 알고 싶다. 동일한 구간을 여러번 칠할 수 있지만, 항상 원하는 색깔로 칠해야 한다.
할 일
다음 minimumInstructions 함수를 구현해야 한다.
minimumInstructions(N, M, K, C, A, B)- 이 함수는 그레이더에 의해 정확하게 한 번 호출된다.- N: 구간의 수를 나타내는 정수.
- M: 일꾼의 수를 나타내는 정수.
- K: 색의 수를 나타내는 정수.
- C: 길이 N인 정수 배열로 각 구간마다 원하는 색깔을 나타낸다.
- A: 길이 M인 정수 배열로 각 일꾼이 좋아하는 색의 수을 나타낸다.
- B: 길이 M인 정수 배열들의 배열로 각 일꾼이 좋아하는 색을 나타낸다.
- 이 함수의 리턴 값은 성렬이가 모든 구간을 원하는 색으로 칠하기 위해 필요한 지령의 최소 개수이다. 만약 이렇게 칠하는 것이 불가능하다면 -1을 리턴한다.
예제
첫번째 예제에서, N = 8, M = 3, K = 5, C = [3, 3, 1, 3, 4, 4, 2, 2], A = [3, 2, 2], B = [[0, 1, 2], [2, 3], [3, 4]]이다. 성렬이는 다음과 같은 지령을 내릴 수 있다.
- x = 1, y = 0. 1번 일꾼이 0번 구간을 칠할 수 있고, 2번 일꾼이 1번 구간을 칠할 수 있고, 0번 일꾼이 2번 구간을 칠할 수 있으므로 이 지령은 타당하다.
- x = 0, y = 2. 0번 일꾼이 2번 구간을 칠할 수 있고, 1번 일꾼이 3번 구간을 칠할 수 있고, 2번 일꾼이 4번 구간을 칠할 수 있으므로 이 지령은 타당하다.
- x = 2, y = 5. 2번 일꾼이 5번 구간을 칠할 수 있고, 0번 일꾼이 6번 구간을 칠할 수 있고, 1번 일꾼이 7번 구간을 칠할 수 있으므로 이 지령은 타당하다.
성렬이가 3개보다 적은 지령으로 모든 구간을 원하는 색깔로 칠할 수 없다는 것을 쉽게 보일 수 있기 때문에, minimumInstructions(8, 3, 5, [3, 3, 1, 3, 4, 4, 2, 2], [3, 2, 2], [[0, 1, 2], [2, 3], [3, 4]])의 리턴값은 3이어야 한다.
두번째 예제에서, N = 5, M = 4, K = 4, C = [1, 0, 1, 2, 2], A = [2, 1, 1, 1], B = [[0, 1], [1], [2], [3]]이다. 3번 일꾼은 색 3만 좋아하는데 색 3으로 칠할 구간이 없기 때문에, 성렬이가 어떤 지령을 내리더라도 무효가 된다. 따라서, minimumInstructions(5, 4, 4, [1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], [1], [2], [3]])의 리턴값은 -1이어야 한다.
제한
0 ≤ k < K에 대해서, f(k)가 j번 일꾼이 색 k를 좋아하는 j의 개수라고 하자. (즉, 색 k를 좋아하는 일꾼의 수이다.) 예를 들어, 만약 f(1) = 2이라면, 색 1을 좋아하는 일꾼이 둘 있다.
- 1 ≤ N ≤ 100000.
- 1 ≤ M ≤ min(N, 50000).
- 1 ≤ K ≤ 100000.
- 0 ≤ C[i] < K.
- 1 ≤ A[j] ≤ K.
- 0 ≤ B[j][0] < B[j][1] < … < B[j][A[j] − 1] < K.
- ∑f(k)2 ≤ 400000.
서브태스크 1 (12점)
- f(k) ≤ 1.
서브태스크 2 (15점)
- N ≤ 500.
- M ≤ min(N, 200).
- ∑f(k)2 ≤ 1000.
서브태스크 3 (13점)
- N ≤ 500.
- M ≤ min(N, 200).
서브태스크 4 (23점)
- N ≤ 20000.
- M ≤ min(N, 2000).
서브태스크 5 (37점)
- 추가적인 제약 조건이 없다.
샘플 그레이더
샘플 그레이더는 입력을 다음 양식으로 읽는다.
N M K C[0] C[1] ... C[N-1] A[0] B[0][0] B[0][1] ... B[0][A[0]-1] A[1] B[1][0] B[1][1] ... B[1][A[1]-1] . . . A[M-1] B[M-1][0] B[M-1][1] ... B[M-1][A[M-1]-1]
샘플 그레이더는 minimumInstructions 함수의 리턴값을 출력한다.
첨부
공개된 그레이더, 예제 케이스, 문제에 대한 기본 파일은 여기에서 받을 수 있다.
제출할 수 있는 언어
C++17, Java 8, C++14, Java 8 (OpenJDK), Java 11, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호