백준 마라톤 (코스43)
(6/8)
이번 주는 시간도 별로 없었고, 도저히 못 풀겠는 문제가 2문제가 있었습니다..
저장해놨다가 나중에 더 강해지면 도전해보자.
Identifying tea (11549, B4)
풀이
숫자 n을 입력 받은 후 a,b,c,d,e를 입력 받는다. a,b,c,d,e 중에서 n과 같은 숫자의 개수를 출력하는 문제이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
bool flag=1;
cin >> n;
int cnt=0;
vector<int>v(5);
for(int i=0;i<5;i++){
cin >> v[i];
if(n==v[i])cnt++;
}
cout << cnt;
return 0;
}
B번 수들의 합 2 (2003, S2)
풀이
수열을 입력 받고, 연속된 구간의 합이 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
29
30
31
32
33
34
35
36
37
38
39
40
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
bool flag=1;
long long l1=0, l2;
cin >> n >> l2;
long long cnt=0;
vector<int> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
l1=v[0];
int l=0, r=1;
while(r<=n){
if(l1==l2){
cnt++;
l1-=v[l];
l++;
}
else if(l1>l2){
l1-=v[l];
l++;
}
else if(l1<l2){
if(r==n)break;
l1+=v[r];
r++;
}
}
cout << cnt;
return 0;
}
C번 Matrix Powers (5095, G4)
풀이
10830 행렬 제곱과 moduler 값만 다르고 완전히 똑같은 문제이다.
분할 정복으로 풀면 된다.
제곱할 행렬 matrix와 답이 될 배열 ans를 만든다.
ans는 단위 행렬로 시작하고, 나머지는 분할 정복 제곱과 똑같다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
bool flag=1;
while(1){
cin >> n >> m >> t;
if(!n && !m && !t)break;
vector<vector<long long>> a(n, vector<long long>(n));
vector<vector<long long>> ans(n, vector<long long>(n, 0));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> a[i][j];
}
ans[i][i]=1;
}
function<void(vector<vector<long long>>&, vector<vector<long long>>&)> matrix =
[&](vector<vector<long long>>& m1, vector<vector<long long>>& m2) {
vector<vector<long long>> temp(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
temp[i][j] += m1[i][k] * m2[k][j];
temp[i][j]%=m;
}
}
}
m1 = temp;
};
while(t>0){
if(t%2==1){
matrix(ans,a);
}
matrix(a,a);
t/=2;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout << ans[i][j] << ' ';
}cout << '\n';
}
cout << '\n';
}
return 0;
}
D번 나누기 (21757, G2)
풀이
수열을 네 부분으로 나눠서 각 부분들의 합이 같도록 만드는 경우의 수를 구하는 문제다.
아이디어는 금방 생각했는데, 투 포인터 문제는 index 맞추는게 항상 헷갈린다.
우선 두 부분으로 나누는 문제로 생각하고, 그런 점들을 다 저장한다.
그 다음 왼쪽 부분과 오른쪽 부분을 반으로 나누는 점들을 찾는다.
두 부분으로 나누는 점의 배열을 middle, 왼쪽 부분을 나누는 점의 배열을 qu_front,
오른쪽 부분을 나누는 점의 배열을 qu_back으로 놨다.
middle 배열을 돌면서 그 점보다 작은 qu_front 점 개수 X 그 점보다 큰 qu_back 점 개수를
모두 더해주면 수열을 네 부분으로 나눠 합이 같도록 만드는 경우의 수가 된다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
bool flag=1;
cin >> n;
long long total=0;
vector<long long>v(n); // 분할 정복으로 풀리려나
for(int i=0;i<n;i++){
cin >> v[i];
total+=v[i];
}
long long res=0;
if(total%4==0){
res = total/4;
}
else{
cout << 0;
return 0;
}
vector<int> middle; // 얘가 total/2를 찾는 좌표임.
vector<int> qu_front; // 얘가 앞에서 total/4를 찾는 좌표임.
vector<int> qu_back; // 얘가 뒤에서 total/4를 찾는 좌표임.
long long at = v[0];
for(int i=1;i<n-2;i++){
at+=v[i];
if(at==res*2){
middle.push_back(i);
}
}
at=0;
for(int i=0;i<n-3;i++){
at+=v[i];
if(at==res){
qu_front.push_back(i);
}
}
at=v[0]+v[1];
for(int i=2;i<n-1;i++){
at+=v[i];
if(at==res*3){
qu_back.push_back(i);
}
}
// for(int i=0;i<middle.size();i++){
// cout << middle[i] << ' ';
// }cout << '\n';
// for(int i=0;i<qu_front.size();i++){
// cout << qu_front[i] << ' ';
// }cout << '\n';
// for(int i=0;i<qu_back.size();i++){
// cout << qu_back[i] << ' ';
// }cout << '\n';
// 앞에서 total/4, 뒤에서 total/4를 찾으면 되는거 아닌가? 투포인터가 더 빠른가
long long ans=0;
int f_l=0;
int b_l=0;
if(qu_back.size()==0 || qu_back.size()==0){
cout << 0;
return 0;
}
for(int i=0;i<middle.size();i++){
while(middle[i]>qu_front[f_l]){
if(f_l == qu_front.size()){
break;
}
f_l++;
}
while(middle[i]>=qu_back[b_l]){
if(b_l == qu_back.size()){
break;
}
b_l++;
}
//cout << f_l << ' ' << b_l << '\n';
ans+= (long long)f_l*(qu_back.size()-b_l);
}
cout << ans;
return 0;
}
E번 돌무더기 게임 1 (24678, G2)
풀이
게임 이론 문제이다.
x, y, z개의 돌 무더기 3개가 있고 번갈아가며 두 개 무더기에서 1개씩 빼고
선택하지 않은 무더기에 돌을 1개 추가한다.
행동할 수 없는 사람이 이긴다.
R이 먼저 시작하고, B가 다음 차례이다.
우선 바로 게임이 끝나는 경우는 x,y,z가 1 1 0과 1 1 1 뿐이다.
이 말은 게임을 진행하다보면 반드시 저 상태로 귀결된다는 것이다.
그러면 각각의 플레이어가 최선을 다할 때 무슨 일이 벌어질까?
미용실에서 머리를 자르면서 곰곰히 생각해보니까 결국 발생하는 일도 몇 개 없다.
우선 돌이 1 1 n개 있을 경우에(n>1) 서로 턴을 번갈아가면서 진행하면 2개가 제거된다.
1명이 y와 z에서 선택해서 빼고 x에 추가하면 2 0 n-1이 되고, 그러면 다음 사람은 x, z를 선택한다.
그러먼 y에 추가가 되니까 1 1 n-2가 된다.
이렇게 2개를 빼는 과정은 2번의 턴이 소모되므로 턴이 바뀌지 않고 진행된다.
또 모든 돌에서 1개씩 빼는 과정이 가능하다.
초기 상태가 3 3 3이라고 할 때 2 2 4, 3 1 3, 2 2 2 이렇게 3번에 걸쳐 모든 돌에서 1개씩 뺄 수 있다.
이 때는 3번의 턴이 소모되므로 턴이 바뀐다.
이제 이 문제는 x,y,z 중 짝수인 수가 몇 개인지를 묻는 문제로 바꿀 수 있다.
x,y,z 중 짝수가 0개
이 말은 전부 홀수라는 뜻이고, 돌을 2개씩 빼는 과정을 거치면 1 1 1인 상태로 R의 차례이다.
그러면 R은 돌을 0 0 2로 만들게 되고 B는 행동할 수 없으니 이긴다.
x,y,z 중 짝수가 1개
역시 돌을 2개씩 빼는 과정을 하면 1 1 0인 상태로 R의 차례이다.
R은 돌을 0 0 1로 만들게 되고, B는 행동할 수 없으니 이긴다.
x,y,z 중 짝수가 2개
여기부터는 달라진다.
돌을 2개씩 빼다보면 0 1 2가 되고, R의 차례이다.
그러면 R은 1 1 0으로 만들고 B가 돌을 0 0 1로 만들게 되므로 R이 이긴다.
x,y,z 중 짝수가 3개
돌을 2개씩 빼다보면 0 2 2가 되고, R의 차례이다.
그러면 R은 1 1 1으로 만들고 B가 돌을 0 0 2로 만들게 되므로 R이 이긴다.
즉, x,y,z 중 짝수가 2개 이상이면 R이 이기고, 아니면 B가 이긴다.
게임 이론 문제는 CTF MISC와 비슷한 맛으로 재밌는 것 같다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
string s;
int ans=0;
bool flag=0;
long long aa, bb, cc;
cin >> t;
int cnt=0;
while(t-->0){
cnt=0;
cin >> a >> b >> c;
if(a%2==0)cnt++;
if(b%2==0)cnt++;
if(c%2==0)cnt++;
if(cnt>=2)cout << "R\n";
else cout << "B\n";
}
return 0;
}
F번 절대적인 스왑 (32957, G2)
풀이
아이디어를 전혀 모르겠어서 태그를 깠더니 세그트리라고 한다.
쿨하게 넘겨줍니다.
세그 트리 진짜 공부해야 하는데 시간이 너무 없다.
1
G번 John’s Math Problem (20505, G1)
풀이
이 문제도 완전 수학 문제였다.
조합론.. 정수론.. 강해져서 돌아올게요..
1
H번 Interstellar Trade (9509, P5)
풀이
그래도 플레 문제는 풀 수 있어서 다행이다.
아이디어가 중요한 문제라서, 이게 맞나? 했는데 맞았다.
우주 지점이 있고, 웜홀을 생성해서 점에서 점까지의 이동하는 모든 거리의 최댓값이
최소가 되도록 하는 문제였다.
웜홀을 생성한다는 것은 우주를 두 부분으로 나누는 것과 같다.
그러면 각 점들에 대해 반복문으로 돌면서 두 부분으로 나눠본다.
두 부분으로 나눴을 때 고려할 거리는 왼쪽 부분끼리의 최대 거리, 오른쪽 부분끼리의 최대 거리,
다른 우주간의 최대 거리가 된다.
max({(v[i]-v[0]+v[n-1]-v[i+1]+1)/2, v[i]-v[0], v[n-1]-v[i+1]}) 를 통해 구할 수 있다.
웜홀은 아무 곳이나 생성할 수 있기에 (두 우주의 끝에서 기준점까지의 거리의 합) / 2가 되기 때문이다.
이 때 소수점은 날려줘야하므로 1을 더했다.
반복문을 돌면서 이 max값이 가장 작을 때가 정답이 된다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
long long n, m, t;
bool flag=1;
cin >> t;
while(t-->0){
cin >> n;
vector<long long> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
sort(v.begin(), v.end());
long long ans = 1e18;
for(int i=0;i<n-1;i++){
ans = min(ans, max({(v[i]-v[0]+v[n-1]-v[i+1]+1)/2, v[i]-v[0], v[n-1]-v[i+1]}));
}
cout << ans << '\n';
}
return 0;
}