이번이 첫 SCPC 도전이다. 본선 진출은 둘째치더라도 1라운드는 2문제만 제대로 풀어도 통과한다는 얘기를 듣고 지금 내 실력이면 통과할 수 있는지 없는지 확인하려는 목적이 강했다.
1라운드 5문제 중 3문제를 pass했다. 라운드 화면을 캡쳐를 못했네..
Q1. 다이어트
풀이 보기
시도 횟수 : 1 / 10
점수 : Pass ( 100 / 100, 1.39675 )
풀이
간단한 정렬 문제이다. $K$개의 메뉴를 각각 1개씩 골라 그것을 먹을 때, 최대의 칼로리의 값의 최솟값을 찾아야 하는 문제이다.
우선 최솟값을 찾아야하므로, 고를 수 있는 $N$개의 메뉴 중 $K+1$번째 이상의 칼로리를 가진 메뉴는 고려대상에서 제외할 수 있다.
메뉴의 집합을 추려내었으면, 그것을 조합하여 최대 칼로리의 합이 최소가 나올 수 있는 경우를 추려내야한다. 나는 양 끝점에서 시작해서 전체를 순회하는 방법을 택했다. 순회하면서 최댓값을 찾아내면, 그것이 가능한 칼로리의 최대 합 중 최소이다.
소스코드
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int Answer;
int main(int argc, char** argv) {
int T, test_case;
cin >> T;
for (test_case = 0; test_case < T; test_case++) {
Answer = 0;
int n, k;
cin >> n >> k;
vector<int> arr_1, arr_2;
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
arr_1.push_back(temp);
}
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
arr_2.push_back(temp);
}
sort(arr_1.begin(), arr_1.end());
sort(arr_2.begin(), arr_2.end());
Answer = arr_1[0] + arr_2[k - 1];
for (int i = 0; i < k; i++)
Answer = max(arr_1[i] + arr_2[k - i - 1], Answer);
cout << "Case #" << test_case + 1 << endl;
cout << Answer << endl;
}
return 0;
}
Q2. 카드 게임
풀이 보기
시도 횟수 : 7 / 10
점수 : Pass ( 150 / 150, 1.97953 )
풀이
전형적인 게임 이론 문제이다. 각 상황에서의 1번 상황을 최대로 만들 수 있는 경우를 찾고, 아니라면 2번 상황이라고 기록하면서 최대한 1번 상황을 만들 방법을 찾아가야한다.
특정 상황에서의 결과를 기록하기 위해 dp를 사용한다. 배열은 3가지 값 중 하나를 가지도록 조정하였다.
- $0$ : 아직 정의되지 않은 부분
- $1$ : 1번 상황 ( $A$가 이길 수 있는 경우 )
- $2$ : 2번 상황 ( A가 어떠한 방법으로도 이길 수 없는 경우 )
testcase마다 모든 칸을 $0$으로 설정하여 정의되지 않은 상태로 바꿔두어야 한다. 카드가 아예 없는 경우는 1번 상황이므로 $1$을 기록하여둔다.
이후 각 카드 더미에서 가져갈 수 있는 카드의 위치까지를 찾는다. 누적합 ( sum_a, sum_b ) 으로 k보다 작거나 같아지는 경우를 찾고, 그때의 index ( a, b ) 를 기록한다. 플레이어는 2개의 카드 더미에서, 각각 ( a개, b개 ) 의 카드를 가져갈 수 있다.
각 플레이어의 입장에서, 상대에게 $2$번 경우를 선택할 수 밖에 없는 경우로 전달해줄 수 있다면 항상 승리할 수 있다. 만약 아니라면, 상대가 자신이 승리하기 위한 $1$번 상황을 따라가기 때문이다. 따라서 현재 상황에서 어떠한 방법을 써도 $2$번 경우로 도달한다면 $1$, 아니라면 $2$를 기록하여야 한다.
이 방법만을 이용하여 dp배열을 모두 채우면 최대 $3001\times 3001$칸의 연산을 수행한다. 각 칸은 ( a, b ) 만큼의 경우의 수를 또 계산하므로 시간초과가 일어난다. 이를 해결하기 위해 1가지 조건을 더 붙인다.
- $2$번 상황에 도달하였다면, 이 상황을 제작할 수 있는 경우에는 그 플레이어가 항상 승리할 방법이 존재한다.
따라서 $2$번 경우를 기록하였다면, 그곳에 도달할 수 있는 모든 칸에는 미리 $1$을 기록하여 연산횟수를 줄인다.
소스코드
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
79
80
81
82
83
84
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX_INDEX 3000
using namespace std;
int result[MAX_INDEX + 1][MAX_INDEX + 1];
int Answer;
int main(int argc, char** argv) {
int T, test_case;
cin >> T;
for (test_case = 0; test_case < T; test_case++) {
Answer = 0;
fill(&result[0][0], &result[MAX_INDEX][MAX_INDEX + 1], 0);
result[0][0] = 1;
int n, k;
cin >> n >> k;
int a = 0, b = 0;
int sum_a = 0, sum_b = 0;
vector<int> arr_1, arr_2;
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
arr_1.push_back(temp);
}
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
arr_2.push_back(temp);
}
for (int i = 0; i <= n; i++) {
if (i > 0) {
sum_a += arr_1[i - 1];
while (sum_a > k)
sum_a -= arr_1[a++];
}
sum_b = 0, b = 0;
for (int j = 0; j <= n; j++) {
if (j > 0) {
sum_b += arr_2[j - 1];
while (sum_b > k)
sum_b -= arr_2[b++];
}
if (result[i][j] > 0) { // if already got result
Answer += (result[i][j] % 2);
}
else {
bool ret = false;
for (int c = a; c <= i && !ret; c++)
ret = (result[c][j] == 2);
for (int c = b; c <= j & !ret; c++)
ret = (result[i][c] == 2);
if (ret)
result[i][j] = 1, Answer++;
else {
result[i][j] = 2;
int sum = 0;
for (int c = i + 1; c <= n && sum + arr_1[c - 1] <= k; c++) {
sum += arr_1[c - 1];
result[c][j] = 1;
}
sum = 0;
for (int c = j + 1; c <= n && sum + arr_2[c - 1] <= k; c++) {
sum += arr_2[c - 1];
result[i][c] = 1;
}
}
}
}
}
cout << "Case #" << test_case + 1 << endl;
cout << Answer << " " << (n + 1)*(n + 1) - Answer << endl;
}
return 0;
}
Q3. 사다리 게임
풀이 보기
시도 횟수 : 4 / 10
점수 : Pass ( 150 / 150, 0.96872 )
풀이
$m$개의 쿼리를 통해 주어진 경로로 가기 위해 부숴야 하는 길의 최솟값을 찾는 문제이다. 직관적으로 BFS로 풀면 답이 나온다. 하지만 10만개의 쿼리를 시간 내에 소화하기란 불가능이다.
쿼리를 통해 답을 도출하는 방법 중, 시간에 큰 제약이 있는 경우 사용하는 방법이 있다. 배열에 정답을 모두 기록하고 하나씩 꺼내 사용하는 방법. 이 문제는 dp를 이용해서 모든 경로에 대한 답을 구해놓은 다음, 쿼리마다 $O(1)$을 이용하여 답을 출력하는 문제였다.
dp배열 matrix[i][j]는 $i$번째 지점부터 $j$번째 지점까지 가기 위해 부숴야하는 길의 최솟값을 기록한다. 이 배열을 이용하여 $k$개의 길에 대한 연산을 모두 마치면, 쿼리의 답을 도출할 수 있는 배열을 만들 수 있다.
배열에서는 아래와 같은 규칙을 이용한다.
- 처음의 모든 dp값은 $-1$이다.
자신으로 가는 경로의 초기값은 $0$이다.
- $a$ -> $b$의 경로 $k$가 주어지면, 아래와 같은 경우로 나누어 계산한다. 가능한 방법 중 최소의 값을 고른다.
matrix[a][b]는matrix[a][a]에서 $k$를 통해 이동하는 방법이 있고, 기존의matrix[a][b]방법에서 $k$ 경로를 부수는 방법이 있다.matrix[b][a]도 위와 같은 방법으로 계산할 수 있다.- $a$ 또는 $b$가 아닌 지점에서 $a$ 또는 $b$ 지점으로 움직이는 경우인
matrix[I][a],matrix[I][b]인 경우에는 각각 길을 부수고 진행할 것인지, 그 길을 사용할 것인지를 선택할 수 있다.
다른 사람들의 후기에서도 기본적으로 dp를 이용하는 방법이 정해인 듯 하다.
소스코드
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 987654321
#define MAX_INDEX 1500
using namespace std;
typedef struct Current {
int pos;
int cur;
int count;
} CR;
typedef struct Line {
int start, end;
} LN;
struct cmp {
bool operator()(CR a, CR b) {
return a.count > b.count;
}
};
int matrix[MAX_INDEX + 1][MAX_INDEX + 1]; // from i to j -> need to break dp line
int Answer;
int main(int argc, char** argv) {
int T, test_case;
cin >> T;
for (test_case = 0; test_case < T; test_case++) {
Answer = 0;
int n, k, m;
cin >> n >> k >> m;
fill(&matrix[0][0], &matrix[MAX_INDEX][MAX_INDEX + 1], -1);
for (int i = 1; i <= n; i++)
matrix[i][i] = 0;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
/* --------------------------------------------------------------------- */
int temp1 = matrix[a][a], temp2 = matrix[a][b];
if (temp2 == -1) {
matrix[a][b] = matrix[a][a]++;
}
else {
matrix[a][b] = min(temp1, temp2 + 1);
matrix[a][a] = min(temp1 + 1, temp2);
}
temp1 = matrix[b][b], temp2 = matrix[b][a];
if (temp2 == -1) {
matrix[b][a] = matrix[b][b]++;
}
else {
matrix[b][a] = min(temp1, temp2 + 1);
matrix[b][b] = min(temp1 + 1, temp2);
}
/* --------------------------------------------------------------------- */
for (int I = 1; I <= n; I++) {
if (I != a && I != b) {
temp1 = matrix[I][a], temp2 = matrix[I][b];
if (temp1 != -1) {
if (temp2 == -1) {
matrix[I][b] = matrix[I][a]++;
}
else {
matrix[I][b] = min(matrix[I][b] + 1, temp1);
}
}
if (temp2 != -1) {
if (temp1 == -1) {
matrix[I][a] = matrix[I][b]++;
}
else {
matrix[I][a] = min(matrix[I][a] + 1, temp2);
}
}
}
}
}
for (; m > 0; m--) {
int a, b;
cin >> a >> b;
Answer += matrix[a][b];
}
cout << "Case #" << test_case + 1 << endl;
cout << Answer << endl;
}
return 0;
}
Q4. 범위 안의 숫자
풀이 보기
시도 횟수 : 10 / 10
점수 : ( 39 / 200, TLE )
풀이
pass받지는 못한 문제이다. 최적화 방법이 생각나지 않아서, 그냥 문제에서 제시하는 조건을 브루트포스를 이용하여 모든 경우를 계산하고 답을 출력하였다.
1번 testcase인 $n≤1000$에서는 작동하지만, $n≤50000$의 범위에서는 제시간안에 절대로 작동할 수 없는 방법이다.
정해를 찾아보니 세그먼트 트리를 이용한다는 듯하다. 예상은 했지만 사용 방법을 몰라 반포기한 감이 없지않은 것 같다.
소스코드
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX_INDEX 50000
using namespace std;
int arr[MAX_INDEX];
int temp_arr[MAX_INDEX];
int Answer;
int main(int argc, char** argv) {
int T, test_case;
cin >> T;
for (test_case = 0; test_case < T; test_case++) {
Answer = 0;
int n, k, m;
cin >> n >> k >> m;
char str[MAX_INDEX + 1] = { 0 };
cin >> str;
int temp = 0, digit = 1;
for (int i = 0; i < k; i++)
temp *= 10, temp += (str[i] - '0'), digit *= 10;
arr[0] = temp;
digit /= 10;
int top = 1;
for (int i = k; str[i] != '\0'; i++) {
temp %= digit, temp *= 10, temp += (str[i] - '0');
arr[top++] = temp;
}
for (int i = 0; str[i]; i++) {
if (str[i] != '1') {
// copy array
for (int a = 0; a < top; a++)
temp_arr[a] = arr[a];
int getdigit = digit;
for (int a = i; a > i - k && a >= 0; a--) {
int quote = temp_arr[a] / getdigit / 10,
remainder = temp_arr[a] % getdigit;
temp_arr[a] = quote * getdigit * 10 + getdigit + remainder;
getdigit /= 10;
}
sort(temp_arr, temp_arr + top);
int start = 0, end = 0;
while (start < top && end < top) {
while (end < top && temp_arr[end] <= temp_arr[start] + m)
end++;
Answer = max(Answer, end - start);
start++;
}
}
}
sort(arr, arr + top);
int start = 0, end = 0;
while (start < top && end < top) {
while (end < top && temp_arr[end] <= temp_arr[start] + m)
end++;
Answer = max(Answer, end - start);
start++;
}
cout << "Case #" << test_case + 1 << endl;
cout << Answer << endl;
}
return 0;
}
결과
E-Z하게 1라운드는 성공했다. 그러나 4번 문제를 풀지 못한 것에서 본선 진출이 가능하다고는 생각하기 힘들어졌다. 시간이 조금 남았으니 문제를 더 풀어봐야겠다.