2018 삼성 대학생 프로그래밍 경진대회(SCPC) 1차 온라인 예선 문제 풀이 + 정답 소스코드 : 네이버 블로그

scpc gatech,scpc satcom,scpc accreditation,scpc registry,scbc climbing,scpc vs tdma,scpc boa vista,scpc login,scpc church,scpc modem,

프로그래밍 대회

2018 삼성 대학생 프로그래밍 경진대회(SCPC) 1차 온라인 예선 문제 풀이 + 정답 소스코드

안경잡이개발자

2018. 6. 24. 11:03

이웃추가

• 본문 폰트 크기 조정 가
• 공감하기
• 공유하기
• URL복사
• 번역하기
• 신고

  방금 막 2018 삼성 대학생 프로그래밍 경진대회(SCPC) 1차 예선이 끝났습니다. 지난 번 예선과 흡사하게 1차 예선은 기초 알고리즘 위주로 출제되었습니다. 저는 문제 4번을 제외한 나머지 문제들만 만점 처리를 받았습니다. 따라서 문제 4번을 빼고 문제 1, 문제 2, 문제 3, 문제 5번에 대한 풀이를 올리고자 합니다. 문제를 푸는 방법은 다양하므로 제 소스코드는 참고용으로 보시면 될 것 같습니다.

문제 1. 버스 타기 (그리디 알고리즘)

문제 설명
- N명의 바둑 선수가 몇 대의 버스에 나누어 타려고 합니다.
- 각 선수는 실력 값을 가지고 있습니다.
- 실력 값이 K 이하로 차이나는 선수끼리는 같은 버스를 탈 수 없습니다.
- 선수의 숫자 N은 1 <= N <= 200,000이고, 실력 차이 K는 1 <= K <= 1,000,000,000입니다. 
- 선수들의 실력을 입력으로 받았을 때 필요한 버스 수의 최소 값을 구하세요.

예제 입력
3
1 1
2
2 3
1 4
5 3
1 5 3 7 9

예제 출력
Case #1
1
Case #2
2
Case #3
2

문제 풀이
- 일단 N의 범위가 200,000이므로 O(N) 혹은 O(N log N)으로 접근해야 합니다.
- 느낌적인 느낌으로 정렬을 수행하고, 그리디(Greedy) 방식으로 풀면 될 것 같았습니다.

  예를 들어 1 3 4 5 7 9로 정렬된 실력 값이 있고, K = 3이라고 해봅시다.

① 1까지 읽었을 때는 문제가 없습니다. ▶ (버스 1대)
② 1 3까지 읽었을 때 1과 3을 비교합니다. 이 때 실력차가 3 이하이네요. ▶ (버스 2대)
③ 1 3 4까지 읽었을 때 이미 버스가 2대 필요한 것을 알고 있으므로 2칸 뒤로 가서 1과 4를 비교합니  다. 이 때 실력차가 3 이하이네요. ▶ (버스 3대)
④ 1 3 4 5까지 읽었을 때 이미 버스가 3대 필요한 것을 알고 있으므로 3칸 뒤로 가서 1과 5를 비교합니다. 그랬더니 실력차가 3보다 컸습니다. 그래서 버스는 그대로 3대입니다. ▶ (버스 3대)
⑤ 1 3 4 5 7까지 읽었을 때 이미 버스가 3대 필요한 것을 알고 있으므로 3칸 뒤로 가서 3과 7을 비교합니다. 그랬더니 실력차가 3보다 컸습니다. 그래서 버스는 그대로 3대입니다. ▶ (버스 3대)
⑥ 1 3 4 5 7 9까지 읽었을 때 이미 버스가 3대 필요한 것을 알고 있으므로 3칸 뒤로 가서 4과 9을 비교합니다. 그랬더니 실력차가 3보다 컸습니다. 그래서 버스는 그대로 3대입니다. ▶ (버스 3대)

  이 원리를 그대로 코드로 옮기시면 됩니다.

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int T, testCase; cin >> T; for(testCase = 1; testCase <= T; testCase++) { int n, k; cin >> n >> k; vector<int> a; for(int i = 0; i < n; i++) { int x; cin >> x; a.push_back(x); } sort(a.begin(), a.end()); int result = 1; for(int i = 1; i < n; i++) { if(a[i] - a[i - result] <= k) result++; } cout << "Case #" << testCase << '\n'; cout << result << '\n'; } return 0; }

문제 2. 회문인 수의 합 (단순 구현)

문제 설명
- 왼쪽에서 읽었을 때와 오른쪽에서 읽었을 때 같은 숫자를 회문이라고 합니다.
- 어떤 수 n이 주어졌을 때, 이 n을 회문인 숫자 최대 3개의 합으로 표현할 수 있는지 판별하세요.
- 표현할 수 있다면 회문인 숫자들의 최소 개수의 합으로 표현하는 프로그램을 작성하세요.
- 121은 그 자체가 회문인 숫자이므로 1개의 회문인 숫자 121로 표현합니다.
- 15233은 2개의 회문인 숫자 13231 2002로 표현합니다.
- 15237은 3개의 회문인 숫자 13231 2002 4로 표현합니다.
- 회문인 숫자 중에서 같은 값이 있는 것도 허용됩니다.
- 회문인 숫자가 여러 개 인 경우 내림차순으로 출력합니다.

예제 입력
2
6
124

예제 출력
Case #1
1 6
Case #2
2 121 3

문제 풀이
- 일단 입력 값 N의 범위가 1 <= N <= 10,000입니다.
- 10,000보다 작은 회문의 갯수는 다 합쳐도 500개가 안될 것 같다고 생각했습니다.
- 따라서 모든 회문을 미리 구해놓은 뒤에 O(N^3)으로 풀었습니다.

#include <iostream> #include <sstream> using namespace std; int circular[10001]; int count; bool isPalindrome(int x) { stringstream ss; ss << x; string str = ss.str(); int len = str.length(); for(int i = 0; i < len; i++) if(str[i] != str[len - 1 - i]) return false; return true; } bool one(int x) { for(int i = 0; i < count; i++) { if(circular[i] == x) { cout << 1 << ' ' << circular[i] << '\n'; return true; } } return false; } bool two(int x) { for(int i = 0; i < count; i++) { for(int j = 0; j < count; j++) { if(circular[i] + circular[j] == x) { cout << 2 << ' ' << circular[j] << ' ' << circular[i] << '\n'; return true; } } } return false; } bool three(int x) { for(int i = 0; i < count; i++) { for(int j = 0; j < count; j++) { for(int k = 0; k < count; k++) { if(circular[i] + circular[j] + circular[k] == x) { cout << 3 << ' ' << circular[k] << ' ' << circular[j] << ' ' << circular[i] << '\n'; return true; } } } } return false; } int main(void) { int T, testCase; for(int i = 0; i <= 10000; i++) { if(isPalindrome(i)) { circular[count] = i; count++; } } cin >> T; for(testCase = 1; testCase <= T; testCase++) { int n; cin >> n; cout << "Case #" << testCase << '\n'; if(!one(n) && !two(n) && !three(n)) { cout << '0' << '\n'; } } }

문제 3. 우주정거장 (DFS)

문제 설명
- 우주정거장은 공 모양의 캡슐들과 각각 두 개의 캡슐을 연결하는 통로들로 만들어집니다.
- 우주정거장이 최종적으로 어떻게 구성될 지는 이미 정해져 있다고 합니다.
- 우주정거장 생성 1단계: 우주 정거장의 최초구성을 지상에서 만들어 궤도에 올립니다.
- 우주정거장 생성 2단계: 아래의 작업이 여러 차례 반복됩니다.
(작업: 이미 통로로 직접 연결된 두 캡슐 A와 B에 대해서 A와 캡슐 X를 통로로 연결하고, B와 X를 통로로 연결합니다. 여기서, 캡슐 X와 두 통로는 우주정거장에 새로 추가되는 것입니다.)
- 1단계에서 만들어 올려야 하는 우주정거장의 최초구성에 포함된 캡슐의 개수가 가장 작은 경우를 찾아봅시다. 동일한 우주정거장의 최종구성에 대해 캡슐이 가장 적은 최초구성은 여러 개일 수 있습니다.
- 임의의 캡슐에서 다른 임의의 캡슐로 1개 이상의 통로를 이용해 이동하는게 보장된다고 가정합니다.
- 서로 다른 한 쌍의 캡슐을 연결하는 통로는 최대 1개입니다.

예제 입력
3
3 3
1 2
3 1
2 3
4 4
1 2
2 3
3 4
1 4
5 6
1 2
2 3
1 4
2 4
2 5
3 5

예제 출력
Case #1
2
Case #2
4
Case #3
3

문제 풀이
- 캡슐의 수 N의 범위는 2 <= n <= 200,000이고 통로의 수 M의 범위는 1 <= M <= 400,000입니다.
- 문제를 풀기 전에 매우 많은 경우의 수를 사전에 고려하는 것이 유용한 문제입니다.

- 특히 위 케이스를 떠올릴 수 있는 것이 매우 중요합니다. 왼쪽 그림은 1, 2, 3, 4는 서로 연결되어 있어 최초구성이 아닌 이상 임의적으로 만들어 질 수 없는 형태입니다. 반면에 오른쪽 그림은 연결된 두 개의 노드로부터 파생될 수 있는 최종구성이므로 최소 크기의 구성이 2개가 되는 것입니다.
- 이를 토대로 생각했을 때 우리가 '찾아야 할' 형태는 3개의 노드로 구성된 삼각형 사이클입니다. 또한 삼각형 사이클 중에서도 연결된 통로가 2개인 노드를 찾아야 합니다. 왜냐하면 '생성 2단계'의 결과로 만들어지는 새로운 노드는 반드시 연결된 통로가 2개이기 때문입니다. 예를 들어 다음과 같습니다.

- 위 경우에서는 5만 지우면 됩니다. 또한 위 그림에서 6이 새롭게 더 추가된다고 가정해봅시다.

- 이렇게 되면 노드 5에 연결된 통로는 3개가 되지만, 먼저 노드 6이 지워진다고 가정하면 다시 노드 5에 연결된 통로는 2개로 줄어들게 될 것입니다. 그래서 하나씩 지워나가 문제를 풀 수 있습니다.
- 다시 말해 연결된 간선이 2개인 모든 노드 중에서 삼각형 사이클을 형성하는 노드를 큐에 담아서 계속해서 지워나가면 해결할 수 있습니다.

#include <iostream> #include <vector> #include <queue> #define MAX 200001 using namespace std; vector<int> a[MAX]; queue<int> q; int result; // 벡터에서 특정한 원소를 찾아 제거합니다. void vectorDrop(int now, int target) { for(int i = 0; i < a[now].size(); i++) { if(a[now][i] == target) { a[now].erase(a[now].begin() + i); } } } // 삼각형 사이클을 발견했을 때 처리하는 함수입니다. void process(int target) { vectorDrop(a[target][0], target); vectorDrop(a[target][1], target); if(a[a[target][0]].size() == 2) { q.push(a[target][0]); } if(a[a[target][1]].size() == 2) { q.push(a[target][1]); } } // DFS를 이용해 삼각형 사이클을 찾습니다. void find(int target, int now, int count) { if(count == 3) { for(int i = 0; i < a[now].size(); i++) { // 삼각형 사이클이 형성되는 경우 if(a[now][i] == target) { result++; process(target); return; } } return; } // 연결된 노드를 DFS 탐색합니다. for(int i = 0; i < a[now].size(); i++) { find(target, a[now][i], count + 1); } } int main(void) { int T; cin >> T; for(int testCase = 1; testCase <= T; testCase++) { for(int i = 0; i < MAX; i++) { a[i].clear(); } result = 0; queue<int> empty; swap(q, empty); int n, m; cin >> n >> m; for(int i = 0; i < m; i++) { int x, y; cin >> x >> y; a[x].push_back(y); a[y].push_back(x); } // 연결된 간선이 2개인 노드를 큐에 삽입합니다. for(int i = 1; i <= n; i++) { if(a[i].size() == 2) { q.push(i); } } // 큐가 비워질 때까지 사이클을 찾아 처리합니다. while(!q.empty()) { int x = q.front(); q.pop(); find(x, x, 1); } cout << "Case #" << testCase << '\n'; cout << n - result << '\n'; } return 0; }

문제 5. Lights to Stage (이분 탐색)

문제 설명
- 2차원 평면에 두 점(0, 0)과 (N, 0)을 연결하는 직선 선분을 무대라고 합니다.
- x좌표 0에서 N 사이의 범위에서 +1과 -1의 기울기를 갖는 선분들이 서로 연결된 것을 다각 선분이라고 합니다.
- 전등을 설치하기 위해 주어진 다각 선분은 y축에 평행한 직선과 최대 한 번만 교차하고, 선분 위의 점들은 모두 y좌표가 0보다 크거나 같습니다.
- 각 전등은 주어진 다각 선분 위의 한 점에 설치 되어야 합니다.
- 다각 선분 위에 있는 점 P = (Px, Py)에 전등을 설치하면 무대 선분의 (Px - Py, 0)에서 (Px + Py, 0)까지 비출 수 있습니다.
- 예를 들어 (0, 0)과 (8, 0)을 연결하는 무대 선분과 세 점 (0 ,1), (4, 5), (8, 1)을 순서대로 연결하는 다각 선분을 좌표평면에 나타내면 다음과 같습니다.

- 이 경우는 (7/2, 9/2) 위치에 전등을 설치해 무대 전체를 비출 수도 있습니다. 또한 (4, 5) 위치에 전등을 설치하여 무대를 비출 수도 있습니다. 아래 두 그림 모두 전등을 다는 방법이 될 수 있습니다.

- 전등을 2개 설치할 수 있는 경우엔 (3/2, 5/2)와 (13/2, 5/2)에 설치해 무대 전체를 비출 수 있습니다.

- 설치할 수 있는 전등이 L개 주어졌을 때, 주어진 전등을 사용하여 무대를 모두 비출 수 있도록 전등을 설치하는 방법이 있다고 가정합니다. 이 때 이러한 설치 방법들 가운데 무대로부터 가장 먼 전등까지의 거리가 가장 작은 설치 방법을 구하여, 이 설치 방법에서 가장 먼 전등까지의 거리를 출력해보세요.
- 무대를 모두 비추는 설치방법이 없다면 -1을 출력하세요.


예제 입력
2
8 2 1
0 1
4 5
8 1
8 2 2
0 1
4 5
8 1

예제 출력
Case #1
9 2
Case #2
5 2

문제 풀이
- 무대 선분 (0, 0)과 (N, 0)에서 N의 범위는 3 <= N <= 1,000,000,000입니다.
- 전등을 설치할 수 있는 다각 선분의 개수 M의 범위는 1 <= M <= 200,000입니다.
- 전등의 개수 L의 범위는 1 <= L <= 200,000입니다.
- 다각 선분을 구성하는 점의 x 좌표는 0 <= x <= N, y 좌표는 0 <= y <= 1,000,000,000,000입니다.
- 연속한 두 정점을 연결하는 직선의 기울기는 +1 혹은 -1입니다.
- 이 문제는 이분 탐색과 그리디 알고리즘을 혼용하여 해결할 수 있습니다.
- 출력할 때 가장 멀리 있는 전등의 y 좌표를 분자와 분모 형태로 출력해야 하지만, 기울기가 +1 혹은 -1이라는 점에서 분모는 2보다 클 수 없습니다. 따라서 입력을 받을 때부터 각 좌표에 2배를 곱합니다.
- 결과적으로 전등이 달릴 수 있는 최대 y 좌표에서 최소 y 좌표 범위에서 이분 탐색을 수행하며 특정한 y 좌표에서 전등을 설치할 수 있는지 확인하면 됩니다.
- 전등을 설치할 수 있는지 확인할 때는 그리디 알고리즘을 이용해 L개의 전등을 이용해 왼쪽에서부터 모든 무대 선분을 채울 수 있는지 확인하면 됩니다.
- 전등 설치 여부를 확인할 때 특정한 기준 y 좌표보다 작은 다각 선분까지 살폈을 때 비로소 최적의 해를 구할 수 있습니다.
- 이 때 시간 복잡도는 O(log y * M)으로 최악의 경우에도 약 40 * 200,000로 해결할 수 있습니다.

#include <iostream> #include <vector> using namespace std; class Line { private: pair<long long int, long long int> p1; pair<long long int, long long int> p2; public: Line(pair<long long int, long long int> p1, pair<long long int, long long int> p2) { this->p1 = p1; this->p2 = p2; } long long int getRange(long long int right, long long int y) { long long int maxY = max(p1.second, p2.second); long long int minY = min(p1.second, p2.second); // Y 좌표를 포함하는 경우 if(minY <= y && maxY >= y) { long long int a = (p2.second - p1.second) / (p2.first - p1.first); long long int b = p1.second - (a * p1.first); long long int left = ((y - b) / a) - y; // 빈 공간 없이 조명을 비출 수 없다면 -1 반환 if(left > right) return -1; // 빈 공간 없이 조명을 잘 비출 수 있다면 오른쪽 상한선 반환 return ((y - b) / a) + y; } // Y 좌표를 포함하지 않는 경우 else { // 큰 Y 좌표가 기준 y보다 작은 경우 if(maxY < y) { long long int a = (p2.second - p1.second) / (p2.first - p1.first); long long int b = p1.second - (a * p1.first); long long int left = ((maxY - b) / a) - maxY; // 빈 공간 없이 조명을 비출 수 없다면 -1 반환 if(left > right) return -1; // 빈 공간 없이 조명을 잘 비출 수 있다면 오른쪽 상한선 반환 return ((maxY - b) / a) + maxY; } // 위 쪽에 있으면 -2 반환 return -2; } } }; vector<Line> lines; long long int n, m, l; bool check(long long int y) { // 0부터 N까지 조명을 비추기 long long int right = 0, now = 0, count = 0; for(long long int i = 0; i < lines.size(); i++) { // 가진 조명의 갯수까지만 설치 가능 if(count == l) break; // 왼쪽 부분을 포함하면서 비출 수 있는지 확인 long long int temp = lines[i].getRange(right, y); // Y 좌표를 포함하지 않는 경우 넘어가기 if(temp == -2) continue; else { // 왼쪽 부분을 비출 수 없다면 if(temp == -1) { // 갱신이 이루어진 경우 반영 if(now != right) { right = now; count++; i--; continue; } // 갱신이 이루어지지 않았다면 else break; } else { now = temp; } } } right = now; // 조명이 전체 범위를 감싸고 있는 경우 if(right >= n) { return true; } return false; } int main(void) { long long int T; cin >> T; for(long long int testCase = 1; testCase <= T; testCase++) { lines.clear(); cin >> n >> m >> l; n *= 2; long long int down = 2000000000001; long long int up = -1; pair<long long int, long long int> p1, p2; long long int x, y; cin >> x >> y; x *= 2, y *= 2; if(y > up) up = y; if(y < down) down = y; p1.first = x, p1.second = y; for(long long int i = 0; i < m; i++) { cin >> x >> y; x *= 2, y *= 2; if(y > up) up = y; if(y < down) down = y; p2.first = x, p2.second = y; lines.push_back(Line(p1, p2)); p1 = p2; } long long int answer = -1; while(down <= up) { long long int mid = (down + up) / 2; if(check(mid)) { answer = mid; up = mid - 1; } else { down = mid + 1; } } cout << "Case #" << testCase << '\n'; if(answer != -1) { if(answer % 2 == 0) cout << answer / 2 << " 1" << '\n'; else cout << answer << " 2" << '\n'; } else { cout << answer << '\n'; } } return 0; }

Link Source : http://m.blog.naver.com/ndb796/221305544177