백준 마라톤 (코스42)
(8/8)
처음 플레 문제가 나왔다. 계속 풀다보니 실력이 느는지 풀만했다.
Haughty Cuisine (20336, B4)
풀이
그냥 입력 받은 것 중 1세트를 출력하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
long long ans;
string s;
cin >> t;
for(int i=0;i<t;i++){
cin >> n;
if(i==0)cout << n << '\n';
for(int j=0;j<n;j++){
cin >> s;
if(i==0)
cout << s << '\n';
}
}
return 0;
}
B번 K-Queen (26006, S2)
풀이
킹 위치랑 퀸 여러개 위치가 주어지고, 체크, 체크메이트, 스테일메이트, none 중에
현재 상황에 해당하는 것을 출력하는 문제이다.
체스 문제 특) 구현할게 너무 많습니다..
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
cin >> n >> m;
cin >> a >> b; //킹 좌표
int check[3][3]={0};
for(int i=0;i<m;i++){
cin >> c >> d;
if(a-1<=c && c<=a+1){
for(int j=0;j<=2;j++){
check[c-a+1][j]=1;
}
}
if(b-1<=d && d<=b+1){
for(int j=0;j<=2;j++){
check[j][d-b+1]=1;
}
}
int dx[9]={-1,-1,-1,0,0,0,1,1,1};
int dy[9]={-1,0,1,-1,0,1,-1,0,1};
for(int j=0;j<9;j++){
if((c-(a+dx[j]))==d-(b+dy[j])){
check[1+dx[j]][1+dy[j]]=1;
}
if((c-(a+dx[j]))==-1*(d-(b+dy[j]))){
check[1+dx[j]][1+dy[j]]=1;
}
}
}
for(int i=-1;i<=1;i++){ //끝자락 확인
for(int j=-1;j<=1;j++){
if(a+i<1 || a+i>n || b+j<1 || b+j>n)check[1+i][1+j]=1;
}
}
bool flag=check[1][1];
int cnt=0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(check[i][j])cnt++;
//cout << check[i][j] << ' ';
}//cout << '\n';
}
if(flag){
if(cnt==9)cout<<"CHECKMATE\n";
else cout << "CHECK\n";
}
else{
if(cnt==8)cout<<"STALEMATE\n";
else cout << "NONE\n";
}
return 0;
}
C번 실질적 약수 (2247, G5)
풀이
N이 주어지면 1~N까지의 각 숫자의 실질적 약수를 더한 값을 구하는 문제다.
N 최대 값이 2억이길래 마침 O(N/2) 풀이가 생각나서 풀었다.
2~N까지 각 수들이 등장하는 횟수는 n/i번이라는 사실을 이용했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
string s;
cin >> n;
m = 200000000;
long long ans=0;
for(int i=2;i<=n/2;i++){
ans += (n/i-1)*i;
ans%=1000000;
}
cout << ans;
return 0;
}
그런데 푼 사람을 보니 0ms인 사람이 많다. O(sqrt(N))도 가능하다는데?
약수 문제일 때 알아챘어야 하는데 n/2로 된다는 것은 당연히 sqrt(N)도 의심했어야 했다.
1
2
3
4
5
for(ll i=2;i*i<=n;i++){
t = n/i;
ans+=(t-i)*i;
ans+=(t-i+1)*(i+t)/2;
}
이렇게 i가 나온 횟수와 i로 나눠진 몫(i~t)까지를 더하면 된다.
이러면 sqrt(N) 시간만에 풀 수 있었네요.
D번 녹색 옷 입은 애가 젤다지? (4485, G4)
풀이
아주 전형적인 다익스트라 문제다.
따로 설명이 필요 없는 기초 예제 문제
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
string s;
a=0;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
while(1){
int ans=0;
a++;
cin >> n;
if(n==0)break;
vector<vector<int>> v(n, vector<int>(n, 1e9));
vector<vector<int>> djk(n, vector<int>(n, 1e9));
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
cin >> v[j][k];
}
}
pair<int, int> p;
djk[0][0]=v[0][0];
priority_queue<pair<int, pair<int, int>>> pq;
pq.push({-v[0][0], {0, 0}});
while(!pq.empty()){
int x = pq.top().second.first;
int y = pq.top().second.second;
int cur = -pq.top().first;
pq.pop();
for(int j=0;j<4;j++){
if(x+dx[j]>=0 && x+dx[j]<=n-1 && y+dy[j]>=0 && y+dy[j]<=n-1){
if(djk[x+dx[j]][y+dy[j]] > cur+v[x+dx[j]][y+dy[j]]){
djk[x+dx[j]][y+dy[j]] = cur+v[x+dx[j]][y+dy[j]];
pq.push({-djk[x+dx[j]][y+dy[j]], {x+dx[j], y+dy[j]}});
}
}
}
}
cout << "Problem " << a << ": " << djk[n-1][n-1] << '\n';
}
return 0;
}
E번 Road Reconstruction (20046, G4)
풀이
신기하게도 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
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;
long long ans=0;
bool flag=0;
cin >> n >> m;
vector<vector<int>> v(n, vector<int>(m));
vector<vector<int>> money(n, vector<int>(m, 1e9));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> v[i][j];
}
}
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
if(v[0][0]==-1){
cout << "-1";
return 0;
}
priority_queue<pair<int, pair<int, int>>> pq;
pq.push({-v[0][0], {0,0}});
money[0][0]=v[0][0];
while(!pq.empty()){
int cur = -pq.top().first;
int x = pq.top().second.first;
int y = pq.top().second.second;
pq.pop();
for(int i=0;i<4;i++){
if(x+dx[i]<0 || x+dx[i]>=n || y+dy[i]<0 || y+dy[i]>=m || v[x+dx[i]][y+dy[i]]==-1)continue;
if(money[x+dx[i]][y+dy[i]] > cur+v[x+dx[i]][y+dy[i]]){
money[x+dx[i]][y+dy[i]] = cur+v[x+dx[i]][y+dy[i]];
pq.push({-money[x+dx[i]][y+dy[i]], {x+dx[i], y+dy[i]}});
}
}
}
if(money[n-1][m-1]==1e9)cout << "-1";
else cout << money[n-1][m-1];
return 0;
}
F번 Frogs (18045, G2)
풀이
스위핑 문제이다.
imos? 라고도 볼 수 있고 애초에 스위핑이 imos랑 거의 비슷하지 않나?
사실 2개에 큰 차이가 있는지도 잘 모르겠다.
이것도 태그를 까고서 겨우 풀 수 있었다.
개구리가 갈 수 있는 제일 왼쪽에 1이라는 flag와 함께 값을 넣어주고
개구리가 갈 수 없는 가장 오른쪽에 -1이라는 flag와 함께 값을 넣어준다.
그 넣어준 값들이 있는 배열을 정렬한 다음 스위핑을 시작하면 된다.
여기서도 구현이 곤란한게 숫자 범위가 200000까지라서 우선순위 큐에서 그냥 뺄 수 없다.
그래서 값이 있는지 없는지 확인하는 map을 하나 더 만들어줫다.
pq에서 값을 빼려는데 map에 값이 없으면 이미 빠진애이므로 그냥 pq.pop()을 해준다.
재밌는 문제인 것 같다.
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
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;
cin >> t;
while(t-->0){
vector<pair<int, pair<int, int>>> v;
map <int,int> mp; //나온애 저장용?
ans=0;
cin >> n;
for(int i=0;i<n;i++){
cin >> a >> b;
v.push_back({max(0, i-a), {1, b}}); //1은 집어넣는거
v.push_back({min(n-1, i+a+1), {-1, b}}); //-1은 빼는거
}
sort(v.begin(), v.end());
priority_queue<int> pq;
for(int i=0;i<v.size();i++){
flag =0;
if(i!=0 && v[i].first!=v[i-1].first){
vector<int> tmp;
while(pq.size()){
if(mp[pq.top()]==0)pq.pop(); //없으면
else{ //있으면
tmp.push_back(pq.top());
mp[pq.top()]--;
pq.pop();
}
if(tmp.size()==3){
ans = max(ans, tmp[0]+tmp[1]+tmp[2]);
pq.push(tmp[0]);
mp[tmp[0]]++;
pq.push(tmp[1]);
mp[tmp[1]]++;
pq.push(tmp[2]);
mp[tmp[2]]++;
flag = 1;
break;
}
}
if(!flag){
for(int j=0;j<tmp.size();j++){
mp[tmp[j]]++;
pq.push(tmp[j]);
}
}
}
if(v[i].second.first==1){
pq.push(v[i].second.second);
mp[v[i].second.second]++;
}
else if(v[i].second.first==-1){
mp[v[i].second.second]--;
}
}
cout << ans << '\n';
}
return 0;
}
G번 Superbull (10479, G1)
풀이
꽤나 인상깊은 문제였다.
아이디어를 알고나니 구현은 엄청 쉬웠는데, 이게 MST 문제라고? 싶었다.
N(1<=N<=2000) 개의 팀을 입력 받고, 두 팀이 경기해서 나온 득점은 N1^N2이다.
진 팀은 떨어지고, 이긴 팀은 계속 게임을 할 수 있는 토너먼트 방식이다.
이 때 총 점수가 가장 크도록 경기를 짰을 때 점수를 출력하는 문제다.
처음에는 이게 xor 성질을 이용하는건가? 싶었지만 전혀 떠오르지 않았다.
그래서 태그를 까보니 MST라는데.. 모르겠어서 editorial을 더 찾아봤다.
그렇게 답지를 보니 어이가 없었는데, 팀들을 각각 node로 놓는다.
그 다음에 승부한 팀들을 간선으로 잇는데, 떨어진 팀은 또 경기를 못하니까 이렇게 그래프를
그리다 보면 만들어지는 형태는 트리 형태가 된다.
그러니까 모든 팀들에 대한 게임 결과 (N*N)개를 각각 간선으로 놓고 그래프를 그린 다음에
node 개수는 2000개 밖에 되지 않으므로 prim 알고리즘으로 답을 구할 수 있다.
이 때 점수의 총 합이 최대이므로, 최대 값을 기준으로 알고리즘을 돌리면 된다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
cin >> n; // tree로 생각을 함. prim 알고리즘 이용
vector<int> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
vector<vector<int>> graph(n);
vector<bool> visit(n,0);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
graph[i].push_back(v[i]^v[j]);
}
}
int visited=0;
priority_queue<pair<int, int>> pq;
pq.push({0, 0});
long long ans=0;
while(visited<n){
int dis = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(visit[cur])continue;
else{
visit[cur]=1;
visited++;
ans += dis;
for(int i=0;i<n;i++){
if(!visit[i])
pq.push({graph[cur][i], i});
}
}
}
cout << ans;
return 0;
}
H번 행운 수 판정 (24441, P5)
풀이
행운 수를 구하는 문제인데 문제 태그가 런타임 전의 전처리이다.
행운 수는 기본적으로 정해져있기에 백만까지의 행운 수를 구하고 풀면 된다.
세그 트리로도 어떻게 할 수 있나본데, 아직 세그 트리를 공부하지 않아서 위의 방법으로 풀었다.
밑의 코드를 실행하면 output.txt에 백만까지의 행운 수가 담기고, 이걸 이용해 풀면 된다.
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
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
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;
bool flag=0;
FILE* f = fopen("output.txt", "w");
vector<bool> v(500000, 0);
for(int i=1;i<=500000;i++){
if(v[i]==0){
b = 2*i+1;
int cnt=0;
for(int j=0;j<500000;j++){
if(v[j]==0)cnt++;
if(cnt==b){
v[j]=1;
cnt=0;
}
}
}
}
cout << v.size();
for(int i=0;v.size();i++){
if(v[i]==0){
fprintf(f, "%d,", 2*i+1);
}
}
return 0;
}