버스타기
N 명의 바둑 선수들이 몇 대의 버스에 나누어 타려고 한다.
선수들은 1부터 N까지 번호가 붙어 있다. 각 선수는 실력 값을 가지고 있다.
선수 i번의 실력 값을 Ai라고 하자.
선수들 간의 경쟁심 때문에 두 선수의 실력 차이가 K이하인 경우는 같은 버스에 타지 않는다고 한다.
즉, 두 선수 i번과 j번의 (i≠j) 실력이 |Ai−Aj|≤K를 만족하는 경우 같은 버스에 타지 않는 것이다.
한 대의 버스에 탈 수 있는 인원은 무제한이라고 한다.
철수는 선수들의 실력을 입력으로 받아서 필요한 버스 수의 최소값을 계산하려고 한다.
여러 선수들이 서로 같은 버스를 타지 않는 관계가 매우 복잡해 보이지만, 철수는 아주 간단한 계산 방법이 있다는 것을 알게 되었다.
철수를 도와서 버스 수의 최소값을 계산하는 프로그램을 작성하라.
- 제한 시간: 전체 테스트 케이스는 50개 이하이며, 전체 수행 시간은 3초 이내. (Java 6초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있습니다.
단, 사용한 출력 함수에 따라서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 될 수 있습니다.
부분 점수를 제대로 받기 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하십시오.
※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB
- 제출 제한 : 최대 10회 (제출 횟수를 반영하여 순위 결정 → 동점자의 경우 제출 횟수가 적은 사람에게 높은 순위 부여)
입력
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어지고,
이후 차례로 T 개의 테스트 케이스가 주어진다. (1≤T≤50)
각 테스트 케이스의 첫 줄에 선수의 인원 수 N(1≤N≤200,000)과 실력 범위 K(1≤K≤1,000,000,000)가 주어진다.
다음 줄에 각 선수의 실력 값이 자연수로 주어진다.
선수들의 실력 값은 1 이상 1,000,000,000 이하의 자연수이며 모두 다르다.
- 점수 : 최대 10회 제출하여 취득한 각각의 점수 중에서 최대 점수 (만점 100점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (27 점) : 이 그룹의 테스트 케이스에서는 N≤5이다.
ㆍ 그룹 2 (73 점) : 이 그룹의 테스트 케이스에서는 별도의 제한이 없다.
출력
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
그 다음 줄에 최소의 버스 대수를 계산하여 출력한다.
입출력예
| 입력 |
|---|
|
| 출력 |
|
|
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
78
|
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int Answer;
int main(){
int T, test_case;
cin>>T;
for(test_case=0;test_case<T;test_case++)
{
Answer=0;
int num_person,gap;
cin>>num_person>>gap;
vector <int> candid;
vector <vector <int> > ads;
int tmp;
for(int i=0;i<num_person;i++){
cin>>tmp;
candid.push_back(tmp);
}
for(int i=0;i<num_person;i++)
{
int sk,flag=0;
//cout<< candid[i];
sk=candid[i];
if(ads.size()==0)
{
vector <int> ad;
ad.push_back(sk);
ads.push_back(ad);
}
else
{
for(int k=0; k<ads.size();k++)
{
for(int l=0;l<ads[k].size();l++)
{
if(abs(ads[k][l]-sk)<=gap)
{
break;
}
if(l==(ads[k].size()-1))
{
flag=1; ads[k].push_back(sk); break;
}
}
if(flag==1)break;
else if(k==(ads.size()-1)&&flag==0)
{
vector <int> ad;
ad.push_back(sk);
ads.push_back(ad);
break;
}
}
}
}
Answer=ads.size();
cout << "Case #" << test_case+1 << endl;
cout << Answer << endl;
}
return 0;
}
|
cs |
위의 코드는 아래와 같이 27점 받고 시간초과가 뜬 코드이다.
| 2019-01-08 15:34 | C++ 14 | Time Limit Exceed | 3.00061 | 16716 | 27 | Code | 비공개 | 0 |
벡터 선언을 잘 못해서 입력값을 넣지못하는 바람에 코드를 작성하는데 시간이 오래걸리기도 했거니와
전체 사람들의 실력 정보를 넣고 이중 벡터를 사용해 분류하였는데 보시다 싶이 3중 포문이 들어가 있어 사람수가 많아지면 시간초과가 떴다ㅜㅜㅜㅜ
보다 효율적인 판단 알고리즘을 생각하다 유튜브의 동빈나씨의 해설강의를 듣고 아래와 같은 초간단 코드를 구현하고 만점을 받았다... 감사합니다 동빈나씨ㅜ
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int Answer;
int main(){
int T, test_case;
cin>>T;
for(test_case=0;test_case<T;test_case++)
{
Answer=1;
int person,gap;
cin>>person>>gap;
vector <int> list;
for(int i=0;i<person;i++){
int tmp;
cin>>tmp;
list.push_back(tmp);
}
sort(list.begin(),list.end());
for(int i=1;i<list.size();i++){
if(list[i]-list[i-Answer]<=gap)Answer++;
}
cout << "Case #" << test_case+1 << endl;
cout << Answer << endl;
}
return 0;
}
|
cs |
실력정보가 들어있는 배열을 오름차순으로 정렬을 하고 버스의 개수만큼 실력차가 최대한 많이 나게 이동한 후 비교하는 방식이다.
결국 필요한 정보는 당장 버스가 더 필요한가? 라는 질문이므로 비슷한 실력(오름차순으로 정렬된 배열에서는 근처에 있는 사람들)이 다 다른버스에 타고 있다는 가정하에 버스의 갯수만큼 배열을 이동한 후 가장 차이가 많이 나는 사람을 비교하면 되는 것이다.
동빈나씨는 이정도 문제는 5-7분이면 해결해야 한다고 말씀하신다..ㅜ 많이 노력해야겠다. 아이디어가 중요하다는 것을 느꼈다.
'Algorithm > 문제 풀이 (Problem Solving)' 카테고리의 다른 글
| [C++] 백준 2309번 일곱난장이 문제풀이 (0) | 2019.02.14 |
|---|---|
| [C++] 백준 1181번 단어정렬 문제풀이 (0) | 2019.01.24 |
| [C++] 코드그라운드 숫자골라내기 문제풀이 (0) | 2018.09.19 |
| [C++] 프로그래머스 가운데 글자 가져오기 문제풀이 (0) | 2018.09.02 |
| [C++] 백준 1002번 터렛 문제풀이 (0) | 2018.08.06 |
댓글