백준 마라톤 (코스87)
(8/8)
1달 동안 백준을 쉬었어서 마라톤을 오랜만에 달려봤다.
원래 플레 문제도 3개 정도는 나왔는데 다 골드가 되었다.
Triple Jump (34646, B1)
풀이
정수 3개 중 아무거나 3번 더해서 만들 수 있는 모든 조합의 수를 준다.
크기 순서대로 a, b, c라고 하면 가장 작은 수는 3*a, 가장 큰 수는 3*b이고
두번째로 작은 수는 2*a+b이므로 간단히 구할 수 있다.
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);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans = 0;
cin >> n;
vector<int> v(n);
for(int i=0;i<n;i++)cin>>v[i];
cout << v[0]/3 << ' ' << v[1]-(v[0]/3*2)<< ' ' << v[n-1]/3;
return 0;
}
B번 Limited Swaps (26874, S1)
풀이
버블 소트를 구현하듯이 풀었다.
수열이 2개 주어지고, 위의 수열을 규칙에 따라 바꿔가며 아래의 수열을 만드는 방법을 출력하게 한다.
규칙은 붙어있는 수가 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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans = 0;
cin >> n;
vector<int> v1(n+1);
vector<int> v2(n+1);
for(int i=1;i<=n;i++)cin>>v1[i];
for(int i=1;i<=n;i++)cin>>v2[i];
vector<int> ansv;
for(int i=1;i<=n;i++){
int j=i;
while(v1[j]!=v2[i]){
j++;
if(j>n){
flag=1;
break;
}
}
int l=i, r=j;
while(l<r){
if(abs(v1[r]-v1[r-1])>=2){
ansv.push_back(r-1);
swap(v1[r], v1[r-1]);
r--;
}
else break;
}
while(l<r){
if(abs(v1[l]-v1[l+1])>=2){
ansv.push_back(l);
swap(v1[l], v1[l+1]);
l++;
}
else break;
}
if(v1[i]!=v2[i])flag=1;
if(flag)break;
}
if(flag){
cout<<"-1";
return 0;
}
cout << ansv.size() << '\n';
string sp="";
for(int i=0;i<ansv.size();i++){
cout << sp << ansv[i];
sp=' ';
}
return 0;
}
C번 나는 기말고사형 인간이야 (23254, G5)
풀이
우선 순위 큐 기본 예제같은 문제로 가장 이득이 되는 점수를 더해주면 된다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans = 0;
cin >> n >> m;
priority_queue<P> pq;
vector<int> base(m);
vector<int> inc(m);
for(int i=0;i<m;i++){
cin >> base[i];
ans+=base[i];
}
for(int i=0;i<m;i++){
cin >> inc[i];
pq.push({inc[i], base[i]});
}
t=24*n;
while(t>0 && !pq.empty()){
int cur=pq.top().first;
int nam=100-pq.top().second;
if(nam==0){
pq.pop();
continue;
}
if(t>nam/cur){
ans+= ((nam/cur)*cur);
t-=(nam/cur);
pq.pop();
pq.push({nam%cur, 100-(nam%cur)});
}
else{
ans+=(t*cur);
t=0;
pq.pop();
}
//cout << "ans : " << ans << ' ' << "t: " << t << '\n';
}
cout << ans;
return 0;
}
D번 Chocolate Giving (6028, 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
49
50
51
52
53
54
55
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans = 0;
cin >> n >> m >> t;
vector<vector<P>> graph(n+1);
priority_queue<P, vector<P>, greater<P>> pq;
vector<int> dst(n+1, 1e9);
dst[1]=0;
for(int i=0;i<m;i++){
cin >> a >> b >> c;
graph[a].push_back({b,c});
graph[b].push_back({a,c});
}
pq.push({0,1});
while(!pq.empty()){
int cur=pq.top().first;
int x=pq.top().second;
pq.pop();
for(int i=0;i<graph[x].size();i++){
int go=graph[x][i].first;
if(dst[go]>dst[x]+graph[x][i].second){
dst[go]=dst[x]+graph[x][i].second;
pq.push({dst[go], go});
}
}
}
// for(int i=1;i<=n;i++){
// cout << dst[i] << ' ';
// }cout<<'\n';
for(int i=0;i<t;i++){
cin >> a >> b;
cout << dst[a]+dst[b]<<'\n';
}
return 0;
}
E번 Coin Toss (4843, G3)
풀이
좀 재밌게 푼 구현 문제다.
격자 판에 동전을 던졌을 때 1칸, 2칸, 3칸, 4칸에 겹칠 확률을 구하는 것이다.
그림을 그려보면 1칸, 2칸은 사각형 모양으로 나오고 4칸은 원 모양으로 나온다.
격자 판이 1xN 형식일 때는 달라지는 값들이 있어서 고려해야 하는게 귀찮았지만 재밌었다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> t;
cout << fixed;
cout.precision(4);
string sp="";
for(int i=1;i<=t;i++){
double x,y,w,r;
cin >> x >> y >> w >> r;
int ggok, mo, na;
double bunmo=x*y*w*w;
if(x>1&&y>1){
ggok=4;
mo=(x+y-4)*2;
na=x*y-mo-ggok;
double t1, t2, t3, t4;
t1=ggok*(w-r/2)*(w-r/2) + mo*(w-r/2)*(w-r) + na*(w-r)*(w-r);
int t2_mo=(x+y-2)*2;
int t2_na=(x-1)*(y-2)+(x-2)*(y-1);
t2=t2_mo*r*(w-r/2)+t2_na*r*(w-r);
int t4_cnt=(x-1)*(y-1);
t4=t4_cnt*PI*(r/2)*(r/2);
t3=bunmo-t1-t2-t4;
cout << sp;
cout << "Case " << i << ":\n";
cout << "Probability of covering 1 tile = " << t1/bunmo*100 << "%\n";
cout << "Probability of covering 2 tiles = " << t2/bunmo*100 << "%\n";
cout << "Probability of covering 3 tiles = " << t3/bunmo*100 << "%\n";
cout << "Probability of covering 4 tiles = " << t4/bunmo*100 << "%\n";
}
else if(x==1&&y==1){
cout << sp;
cout << "Case " << i << ":\n";
cout << "Probability of covering 1 tile = " << 100.0000 << "%\n";
cout << "Probability of covering 2 tiles = " << 0.0000 << "%\n";
cout << "Probability of covering 3 tiles = " << 0.0000 << "%\n";
cout << "Probability of covering 4 tiles = " << 0.0000 << "%\n";
}
else{
ggok=2;
mo= max(x-2, y-2); //긴쪽에서 2개 뺸거니까
double t1=ggok*w*(w-r/2)+mo*(w-r)*w;
cout << sp;
cout << "Case " << i << ":\n";
cout << "Probability of covering 1 tile = " << t1/bunmo*100 << "%\n";
cout << "Probability of covering 2 tiles = " << 100-(t1/bunmo)*100 << "%\n";
cout << "Probability of covering 3 tiles = " << 0.0000 << "%\n";
cout << "Probability of covering 4 tiles = " << 0.0000 << "%\n";
}
sp='\n';
}
return 0;
}
F번 to Pay Respects (31151, G3)
풀이
무기 데미지, 힐량, 횟수가 주어지고 줄 수 있는 최대 데미지를 구하는 문제다.
고민해야 하는 것은 힐 스택이 쌓여있을 때 독을 사용하면 힐 스택이 감소한다는 것이다.
수식으로 접근했는데 i번째에 독을 쓸 때 독의 총 데미지는 (a-i)*d지만 후에 힐이 될 수 있다.
그래서 나중에 힐에 맞춰서 독을 쓰는 것과, 독을 일찍 쓰고 힐을 받게 하는 것. 무엇이 이득인지 봐야한다.
만약 독 포인트가 있을 때 힐 턴이 오면 무조건 독을 쓰고, 아니면 수식으로 확인해줬다.
디버깅하면서 의식의 흐름대로 코드를 고치다보니 풀렸다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans = 0;
cin >> a >> b >> c >> d >> n; //턴 횟수, 무기 뎀, 힐량, 독양, 독 횟수
string s;
cin >> s; //1이면 힐쓴거
ans+= a*b;
vector<int> v;
for(int i=0;i<a;i++){
if(s[i]=='1')v.push_back(i);
}
int idx=0;
int r_p=0, p_p=0;
vector<int> poison; //여기에 도달하면 독을 넣기
int pidx=0;
for(int i=0;i<a;i++){
// i번째에 독을 쓰는 것은 독 총 데미지는 (a-i)*d가 들어가지만
// 후에 k번째에 힐이 있다면 (a-k)*c의 힐이 됨.
//k번째에 독을 맞춰쓰면 (a-k)*d만큼의 데미지를 줌.
if(pidx<poison.size() && i==poison[pidx]){
p_p++;
pidx++;
ans+= (p_p*d-r_p*c);
continue; //여기서도 무조건 넘겨야함.
}
if(n>0){ // 독 포가 있을 때
if(idx<v.size() && v[idx]==i){ //힐할땐
idx++;
p_p++;
n--;
}
else{
if(idx<v.size() && (v[idx]-i)*d > (a-v[idx])*c){
p_p++;
n--;
}
else if(idx<v.size() && (v[idx]-i)*d <= (a-v[idx])*c){
poison.push_back(v[idx]);
idx++;
n--;
i--; //이 때는 다시 확인을 해야할 듯. 그냥 뒤에 있는 힐 타이밍을 지운거니까
continue;
}
else{
p_p++;
n--;
}
}
}
else{
if(idx<v.size() && v[idx]==i){
idx++;
r_p++;
}
}
//cout << "i: " << i << ' ' << "p_p: " << p_p << ' ' << "r_p: " << r_p << '\n';
ans+= (p_p*d-r_p*c);
}
cout << ans;
return 0;
}
G번 원 이동하기 1 (22946, G2)
풀이
풀이는 앞의 글에 쓴 원 이동하기 2와 비슷하다.
다만 x,y 좌표가 있기에 둘 다 고민해서 내부에 들어온 원끼리 간선 관계로 묶어주고
가장 많이 원에 접하는 선을 그엇을 때 횟수는 위의 트리의 지름의 길이와 같다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> n;
struct cir{
double x;
double y;
int r;
};
vector<cir> v(n);
for(int i=0;i<n;i++){
cin>>v[i].x>>v[i].y>>v[i].r;
}
sort(v.begin(), v.end(), [](cir A, cir B){
return A.r<B.r;
});
// for(int i=0;i<n;i++){
// cout << v[i].x << ' ' << v[i].y << ' ' << v[i].r << '\n';
// }
vector<vector<int>> graph(n+1);
for(int i=0;i<n;i++){
for(int j=i+1;j<=n;j++){
if(j==n){ //좌표평면이랑 있다는거
graph[0].push_back(i+1);
graph[i+1].push_back(0);
}
else{
if((sqrt((v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y)))<abs(v[i].r-v[j].r) || (v[i].x==v[j].x && v[i].y==v[j].y)){ //동심원
graph[i+1].push_back(j+1);
graph[j+1].push_back(i+1);
break;
}
}
//cout << sqrt((v[i].x-v[j].x)*(v[i].x-v[j].x)+((v[i].y-v[j].y)*(v[i].y-v[j].y))) << ' ' << abs(v[i].r-v[j].r) << '\n';
}
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<graph[i].size();j++){
// cout << graph[i][j]<<' ';
// }cout<<'\n';
// }
vector<int> vis(n+1, 0);
queue<int> q;
q.push(1);
vis[1]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<graph[x].size();i++){
if(vis[graph[x][i]])continue;
q.push(graph[x][i]);
vis[graph[x][i]]=vis[x]+1;
}
}
int nex=-1;
int mi=-1;
for(int i=0;i<=n;i++){
if(mi<vis[i]){
mi=vis[i];
nex=i;
}
//cout << vis[i]<< ' ';
vis[i]=0;
}//cout<<'\n';
q.push(nex);
vis[nex]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<graph[x].size();i++){
if(vis[graph[x][i]])continue;
q.push(graph[x][i]);
vis[graph[x][i]]=vis[x]+1;
}
}
ans=-1;
for(int i=0;i<=n;i++){
if(ans<vis[i])ans=vis[i];
//cout << vis[i]<< ' ';
}
cout << ans-1;
return 0;
}
H번 출근 기록 2 (14243, G1)
풀이
문제를 보자마자 그리디로 해야겠다고 생각했는데, 출근 기록 1문제를 보면 조건에서 N이 더 작다.
풀이를 보면 백트래킹으로도 풀리는 것 같긴 한데 그리디로 푸는게 더 좋은 방법이니까
b는 일한 후 1일 쉬어야하고, c는 일한 후 2일 쉬어야한다.
일단 a는 아무때나 쓰면 된다.
포인트는 b나 c가 1개 남았으면 들어갈 수 있는 조건에서는 a와 다르지 않게 적용이 된다는 것
배열 첨에 b, c가 들어갈 때 인덱스 계산을 해주기 귀찮아서 AA를 넣고 시작했다.
이제 처음에는 일단 c->b->a로 채우되 1개 남았을 때만 잘 고려해주자 라고 생각을 했는데
cbabcba 뭐 이런 식으로 되야만 하는 예제가 있었다.
위의 예제가 발생하는 경우는 a보다 b가 많아서 b를 빠르게 털어줘야하는 경우이다.
그렇기에 b>a일 때는 b를 먼저 사용하고 나머지는 처음 생각했던대로 구현하니 풀렸다.
증명을 하라고 하면 정확히는 모르겠지만 Proof by AC..
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans = 0;
string s;
cin >> s;
a=0, b=0, c=0;
for(int i=0;i<s.size();i++){
if(s[i]=='A')a++;
if(s[i]=='B')b++;
if(s[i]=='C')c++;
}
string anss="AA";
//그리디하게 넣을 때 b나 c가 1개 남았으면 a와 다르지 않음
//AA를 넣고 시작하는게 편할 듯
for(int i=2;i<s.size()+2;i++){
if(b>1 && b>a && anss[i-1]!='B'){
anss.push_back('B');
b--;
}
else if(c>1 && anss[i-1]!='C' && anss[i-2]!='C'){
anss.push_back('C');
c--;
}
else if(b>1 && anss[i-1]!='B'){
anss.push_back('B');
b--;
}
else if(c==1 && anss[i-1]!='C' && anss[i-2]!='C'){
anss.push_back('C');
c--;
}
else if(b==1 && anss[i-1]!='B'){
anss.push_back('B');
b--;
}
else if(a>=1){
anss.push_back('A');
a--;
}
else{
flag=1;
break;
}
//cout << "i: " << i << ' ' << anss << '\n';
}
if(flag)cout<<-1;
else{
for(int i=2;i<anss.size();i++){
cout<<anss[i];
}
}
return 0;
}