[문제1] 대탈주
[시간제한]
30 개의 테스트 케이스를 합쳐 1초
[메모리제한]
512MB
[문제]
절대로 탈출할 수 없다고 알려진 감옥에서 죄수들이 탈출했다. 이들은 감옥 근처에 세워져 있던 차
를 훔쳐서 도주하고 있으며, 총 N대의 차량을 이용하고 있다. 이 차량들에 대한 정보라고는 각각의
차량의 색상 뿐이다. 즉, 빨간 차는 몇 대, 파란 차는 몇 대, … 와 같다.
죄수를 추적하던 경찰은 다음과 같은 가정을 하게 되었다.
죄수들은 차량을 이용하여 수도로 이동할 것이다. 그런데, 감옥에서 수도로 이동하려면 반드시 특정
한 톨게이트를 지나야 한다.
이들은 도로 정보를 잘 모르기 때문에, 사이에 다른 차가 끼면 뒤의 차는 앞 차를 놓치고 길을 잃게
된다. 따라서 반드시 이들은 한 줄로 붙어서 이동할 것이다. 죄수들의 차량간 순서는 알 수 없다.
따라서 경찰은 해당 톨게이트를 조사하여, 이 날 이 톨게이트를 통과한 모든 차량에 대한 정보를 얻
을 수 있었다. 이 상황에 대한 예를 들어보자. 차량의 색상은 1~9 사이의 숫자로 주어지고, 죄수들
이 타고 있는 차량은 1번 색상 2대, 3번 색상 1대, 7번 색상 1대이다. 한 편 이 날 톨게이트를 통과
한 차량은 모두 N=10 대이며, 통과한 순서대로 차량의 색상을 보면 다음과 같다.
1 2 8 7 1 3 1 1 2 5
이를 보면, 4번째부터 7번째 차량들의 색상이 각각 7, 1, 3, 1이므로 죄수들이 타고 있는 차량의 색상
과 수와 일치한다. 즉 죄수들은 이미 이 톨게이트를 통과했다고 생각할 수 있다.
죄수들이 톨게이트를 통과했는지 여부를 구하는 프로그램을 작성하시오.
[제한 조건]
톨게이트를 통과한 차량의 수 : N
존재할 수 있는 차량의 색상 수 : M
라고 할 때 10개의 입력에 대한 제한 조건은 다음과 같다.
1 ≤ N ≤ 1000
1 ≤ M ≤ 50
M ≤ N
T ≤ 30
[입력]
첫 줄에 테스트 케이스의 개수 T가 주어지고 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스는 3개의 줄로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 정수 N과 M이 공백
으로 구분되어 차례로 주어지며 그 다음줄에 M개의 정수가 공백으로 구분되어 주어지는데 이 M개
의 정수는 차례대로 죄수들이 타고 있는 차량의 개수를 나타내는데 입력받는 순서대로 1번 색상의
차량 개수, 2번 색상의 차량 개수, … , M번 색상의 차량 개수 를 의미한다. 그 다음줄에는 N개의 정
수가 공백으로 구분되어 주어지는데, 각각 차례대로 톨게이트를 통과한 차량의 색상을 나타낸다.
[출력]
총 T 개의 줄이 출력된다. 각 줄은 #x로 시작하고 (x는 테스트 케이스 번호, 1부터 시작) 공백을 하
나 둔 다음, 조건을 만족하는 죄수들의 차량이 몇 번째 차량부터인지 출력한다. 이 떄 톨게이트를
맨 처음 통과한 차량을 1번째로 한다.(0번째가 아니다.) 만약 죄수들이 톨게이트를 통과하지 않았다
면 0을 출력한다.
[입출력 예]
(입력)
3
10 9
2 0 1 0 0 0 1 0 0
1 2 8 7 1 3 1 1 2 5
10 3
2 2 2
1 1 2 2 3 1 1 2 3 3
3 3
3 0 0
1 2 3
(출력)
#1 4
#2 4
#3 0
==================================================
##풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
/*
[]
문제:
접근: 완탐 -> 이중 ㅏㄴ복으로 연속된 m개의 차량 탐색 -> 시간복잡(n*m)
시간복잡도: O(n*m) =
풀이:
1.
*/
#define MAX 1000+2
int m, n, t, sum = 0;
int colorAr[52], carAr[MAX];
int tp[52];
int main() {
ios::sync_with_stdio(false); // 계산시간 단축 // cin,scanf 같이 쓰면 오류
cin.tie(nullptr); cout.tie(nullptr);// 입출력 시간 단축 // 이것을 쓰면 scanf,printf섞어 쓰면 안됨
cin >> t;
for (int i = 1; i <= t; i++) {
int ok = 0;
cin >> n >> m;
// 범죄차량 색 입력
sum = 0;
for (int j = 1; j <= m; j++) {
cin >> colorAr[j];
sum += colorAr[j]; // 차량 총 수
}
// 톨게이트 차량 색 입력
for (int j = 1; j <= n; j++) {
cin >> carAr[j];
}
// 완탐으로 연속 차량 탐색
for (int j = 1; j <= n - sum; j++) {
for (int k = j; k < j + sum; k++) {
tp[carAr[k]]++;
}
// 차량 색 수 일치 검사
int c = 0;
for (int k = 1; k <= m; k++) {
if (tp[k] == colorAr[k]) { c++; }
}
// 맞으면 출력 하고 중지
if (c == m) {
cout << '#' << i << " ";
cout << j << '\n';
ok = 1;
break;
}
//tp배열 초기화
for (int k = 1; k <= m; k++) {
tp[k] = 0;
}
}
// 범죄차량 없으면 0 출력
if (ok == 0) {
cout << '#' << i << " ";
cout << 0 << '\n';
}
}
return 0;
}
|
cs |