Atcoder Beginner Contest #182
대회 링크 : atcoder.jp/contests/abc182
A - twiblr
[문제]
twiblr 라는 sns 에서 추가할 수 있는 최대 팔로잉 수를 구하라.
[풀이]
문제에서 나온 그대로
A, B가 주어졌을 때 (2 * A + 100) - B 를 구하는 간단한 문제입니다.
[코드]
|
1
2
3
4
5
6
7
8
9
10
11
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int a, b; cin >> a >> b;
cout << (a * 2) + 100 - b << "\n";
return 0;
}
|
cs |
B - Almost GCD
[문제]
정수로 이루어진 길이가 N인 수열 A가 있을 때
2이상의 정수 중 가장 수열 A의 원소들과 많이 나누어 떨어지는 수 k를 구하라.
[풀이]
우선 k를 구하기 위해서 최대공약수(GCD)의 성질을 생각해보면
어떤 수 Ai에 대한 gcd k는 Ai보다 반드시 작아야 한다는 걸 알 수 있습니다.
그렇다면, 문제 제한 상 Ai는 max 1000 밖에 안되기 때문에 그냥 2 ~ 1000 까지 N만큼 순회하며
몇 개나 나누어 떨어지는지 구하면 됩니다.
시간 복잡도 : O(N)
[코드]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
vector<int>v(n);
for (int i = 0; i < n; i++) cin >> v[i];
vector<pair<int, int> >ans;
for (int i = 2; i <= 1000; i++)
{
int cnt = 0;
for (int j = 0; j < n; j++)
{
if (v[j] % i == 0) cnt++;
}
ans.push_back({ cnt, i });
}
sort(ans.begin(), ans.end());
cout << ans[ans.size() - 1].second << "\n";
return 0;
}
|
cs |
C - To3
[문제]
"0"이 없는 정수 N이 주어졌을 때
아무데나 1자리씩 지울 수 있는 활동을 할 수 있다고 가정하자.
정수 N이 3의 배수가 되기 위해서 이 활동을 최소 몇 번 해야하는가?
[풀이]
저번 atcoder #181 에서도 나온 문제랑 비슷한데, atcoder는 n의 배수를 좀 좋아하는 듯 합니다.
이 문제를 풀기 위해서도 역시 3의 배수 판별법을 알아야 하는데, 생각보다 간단합니다.
3의 배수 판별법 : 모든 자릿수의 합이 3이 배수이면 됩니다.
따라서 최대 long long 범위인 N을 string으로 받고, 각 자릿수를 더한 값을 sum이라 하면,
case1) sum % 3 == 0
더 볼 것도 없이 N은 이미 3의 자릿수입니다.
case2) sum % 3 == 1
이 경우 정수 N을 구성하는 자릿 수 중 3으로 나눈 나머지가 1인 수 (1, 4, 7)를 찾으면 답이 1이고, 만약 없다면 3으로 나눈 나머지가 2인 수를 2개 찾으면 답을 2로 고정시킬 수 있습니다. ex. (5 + 8) % 3 == 1
case3) sum % 3 == 2
case 2와 비슷한데, 찾아야하는 나머지 수를 반대로 바꾸면 됩니다.
-> 만약 case 2, 3에서 이들을 찾을 수는 있는데, 이들을 빼버리면 아예 N이 사라지는 경우 -1을 답으로 도출하면 됩니다. ex) 11
시간복잡도 : O(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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
string s; cin >> s;
int sum = 0;
for (int i = 0; i < s.size(); i++) sum += s[i] - '0';
int ans = 0;
if (sum % 3 == 1)
{
int tmp_sum = sum;
int cnt = 0;
bool flag = false;
for (int i = 0; i < s.size(); i++) {
if ((s[i] - '0') % 3 == 1) {
if (sum - (s[i] - '0') < 3) continue;
flag = true;
ans = 1;
break;
}
}
if (!flag)
{
for (int i = 0; i < s.size(); i++)
{
if ((s[i] - '0') % 3 == 2) cnt++;
}
if (cnt >= 2) {
if (s.size() > 2) {
ans = 2;
flag = true;
}
}
}
if (!flag) ans = -1;
}
else if (sum % 3 == 2)
{
int cnt = 0;
bool flag = false;
for (int i = 0; i < s.size(); i++) {
if ((s[i] - '0') % 3 == 2) {
if (sum - (s[i] - '0') < 3) continue;
flag = true;
ans = 1;
break;
}
}
if (!flag)
{
for (int i = 0; i < s.size(); i++)
{
if ((s[i] - '0') % 3 == 1) cnt++;
}
if (cnt >= 2) {
if (s.size() > 2) {
ans = 2;
flag = true;
}
}
}
if (!flag) ans = -1;
}
cout << ans << "\n";
return 0;
}
|
cs |
D - Wandering
[문제]
음수가 포함된 정수 N개로 구성된 수열 A가 주어졌을 때
로봇은 직선 좌표계 상에서 다음과 같은 활동을 할 수 있다.
- A1 만큼 좌표 이동
- A1 만큼 이동 후, A2 만큼 이동
- A1, A2 ... An 만큼 이동
이 과정속에서 로봇의 최대 좌표값을 구하시오.
[풀이]
이 문제는 좌표계라는 것을 이해하는데 시간이 조금 걸렸네요
우선 문제 조건 상 N 제한이 20만이기 때문에
완전탐색 형식으로 한칸, 한칸 전진하는 방식을 사용하면 O(N!) 시간복잡도가 걸립니다. 그럴 필요도 없구요
핵심은 처음엔 A1, 두 번째는 A1 ~ A2, 세 번째엔 A1 ~ A3 ... A1 ~ An 과 같이
순서대로 한 칸씩 더한다는 점을 보고 부분합 문제임을 파악하면 됩니다.
따라서 pre[i] : 0 ~ i 번 index까지의 합을 미리 구해두면
n번째까지 로봇이 움직임을 수행했을 때, 위치하는 좌표값을 O(1) 시간에 파악가능합니다.
하지만 여기 함정이 조금 있는데, 로봇이 움직임을 수행하는 중에 최대값이 나올 수도 있다는 점입니다.
만약 A = [2, -1, -2] 인 경우
pre = [2, 1, -1] 이라 1차원적으로 보면 최대값은 3이지만
로봇이 2번째까지 움직인 후(3인 상태), 한 칸 전진하면 최대값인 5가 나올 수 있습니다.
따라서, 부분합들 중 최대값을 구하고, 정답에 업데이트 시키면 됩니다.
p_max[i] = max(pre[0] ~ pre[i])
시간복잡도 : O(N)
[코드]
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pre[200010];
ll p_max[200010];
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
vector<ll>v(n);
for (int i = 0; i < n; i++) cin >> v[i];
pre[0] = v[0]; p_max[0] = v[0];
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1] + v[i];
p_max[i] = max(p_max[i - 1], pre[i]);
}
ll ans = 0, tmp_ans = 0;
for (int i = 0; i < n; i++)
{
tmp_ans += p_max[i];
ans = max(tmp_ans, ans);
tmp_ans -= p_max[i];
tmp_ans += pre[i];
}
cout << ans << "\n";
return 0;
}
|
cs |
E - Akari
[문제]
H * w 격자판과 그 안에
동서남북 4방향을 비추는 전구의 위치와, 전구를 차단하는 벽의 위치가 주어진다.
전구는 4방향으로 벽이 만날 때 까지 인접한 벽을 비출 수 있다고 한다.
이 경우, 전구가 있는 곳을 포함하여 전구가 통하는 벽은 총 몇 칸인가?
[풀이]
우선, 문제 제한부터 보자면 격자판은 최대 1500 * 1500 개의 칸을 가질 수 있습니다.
또한 전구의 위치는 최대 50만개라서
전구의 위치마다, bfs 형식으로 4방향을 비추면 최악의 경우 O(1500^3) 정도의 시간이 걸립니다.
따라서, 이 문제 또한 전처리를 잘 해주어야하는데
격자판의 각 칸을 T라고 하면, 이 칸은 좌표 뿐만 아니라 여러가지 정보를 담고 있다고 합시다.
- 전구의 불빛이 상, 하, 좌, 우로 빠져나간 적이 있는지?
- 전구가 위치하는지, 벽이 위치하는지, 아니면 비어있는 공간인지
- 불빛이 들어온 적이 있는지
여기서 전구의 불빛이 빠져나간지 확인하는 것이 핵심인데
만약 모든 칸에 전구가 있는 4 by 4 격자판이 있는 경우
(1, 1)에서 오른쪽으로 불빛을 이미 쏜 것을 확인했는데, (1,2)에서 다시 한 번 확인하지 않게 해주는 효과가 있습니다.
이는 격자판이 더 커지면 커질 수록 상당히 시간복잡도가 단축되겠죠.
이 방식을 이용하면 각 칸마다 최대 4번만 확인하면 되기 때문에
시간복잡도는 최대 O(4 * N^2) 만큼 소요됩니다.
[코드]
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct box {
bool up = false;
bool down = false;
bool left = false;
bool right = false;
bool state = false;
int cmd = 0; //(0 : 아무것도없음, 1: 전구, 2: 벽)
};
box arr[1501][1501];
int h, w, n, m;
// 상, 하, 좌, 우
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin >> h >> w >> n >> m;
for (int i = 0; i < n; i++)
{
int y, x; cin >> y >> x;
arr[y-1][x-1].cmd = 1;
arr[y-1][x-1].state = true;
}
for (int i = 0; i < m; i++)
{
int y, x; cin >> y >> x;
arr[y-1][x-1].cmd = 2;
}
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (arr[i][j].cmd == 1)
{
arr[i][j].up = true;
arr[i][j].down = true;
arr[i][j].left = true;
arr[i][j].right = true;
//up
for (int k = i - 1; k >= 0; k--)
{
if (arr[k][j].cmd == 2) break;
if (arr[k][j].up) break;
arr[k][j].up = true;
arr[k][j].state = true;
}
//down
for (int k = i + 1; k < h; k++)
{
if (arr[k][j].cmd == 2) break;
if (arr[k][j].down) break;
arr[k][j].down = true;
arr[k][j].state = true;
}
//left
for (int k = j - 1; k >= 0; k--)
{
if (arr[i][k].cmd == 2) break;
if (arr[i][k].left) break;
arr[i][k].left = true;
arr[i][k].state = true;
}
//right
for (int k = j + 1; k < w; k++)
{
if (arr[i][k].cmd == 2) break;
if (arr[i][k].right) break;
arr[i][k].right = true;
arr[i][k].state = true;
}
}
}
}
int ans = 0;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (arr[i][j].state) ans++;
}
}
cout << ans << "\n";
return 0;
}
|
cs |
F - Valid payments
F번은 에디토리얼 풀리면 적어두겠습니다!