백준 마라톤 (코스43)
(8/8)
오랜만에 전부 풀었다.
Polynomial Showdown (4682, S4)
풀이
9개의 정수를 입력받아서 각각의 정수가 차수인 8차 방정식을 출력하는 문제다.
-1, 1, 0이 나올 때 조건문으로 처리하는 과정이 아주 귀찮았다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
using P=pair<int,int>;
long long a, b, c, d;
long long ans = 0;
vector<int> v(9);
while(cin >> v[8]){
for(int i=7;i>=0;i--)cin>>v[i];
for(int i=8;i>=2;i--){
if(v[i]==0)continue;
else{
if(flag==0){
flag=1;
if(v[i]==1)cout <<"x^"<<i<<' ';
else if(v[i]==-1)cout << "-x^" << i << ' ';
else cout << v[i]<<"x^"<<i<<' ';
}
else{
if(v[i]<0){
if(abs(v[i])==1) cout << " - " << "x^" << i << ' ';
else cout << "- " << abs(v[i]) << "x^" << i <<' ';
}
else{
if(v[i]==1)cout << "+ " << "x^" << i <<' ';
else cout << "+ " << v[i] << "x^" << i <<' ';
}
}
}
}
if(v[1]==0){
}
else if(!flag){
flag=1;
if(v[1]==1)cout <<"x" << ' ';
else if(v[1]==-1)cout << "-x" << ' ';
else cout << v[1] <<"x" << ' ';
}
else{
if(v[1]<0){
if(abs(v[1])==1) cout << "- " << "x";
else cout << "- " << abs(v[1]) << "x" << ' ';
}
else if(v[1]>0){
if(v[1]==1)cout << "+ " << "x" <<' ';
else cout << "+ " << v[1] << "x" <<' ';
}
}
if(v[0]==0){
}
else if(!flag){
flag=1;
cout << v[0];
}else{
if(v[0]<0){
cout << "- " << abs(v[0]);
}
else if(v[0]>0){
cout << "+ " << v[0];
}
}
if(!flag)cout<<"0";
cout << '\n';
flag=0;
}
return 0;
}
B번 저울 추 만들기 (2205, G5)
풀이
n에서부터 1까지 모든 추를 사용해서 만들어야 한다.
n이 2^x+k일 때 더해서 2의 거듭 제곱이 되려면 2^x-k를 더한다.
n-1은 2^x+k-1이고 2^x-k+1을 더하면 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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
using P=pair<int,int>;
long long a, b, c, d;
long long ans = 0;
cin >> n;
vector<int> ansv(n+1, 0);
vector<bool> chk(n+1, 0);
for(int i=n;i>=1;i--){
if(!flag){ // 위치 찾고
k=1;
flag=1;
while(k<=i){
k*=2;
}
k-=i;
}
ansv[i]=k;
chk[k]=1;;
k++;
if(k>n || chk[k]){
flag=0;
}
}
for(int i=1;i<=n;i++){
cout << ansv[i] << '\n';
}
return 0;
}
C번 Plus Minus Four Squares (30538, G5)
풀이
a^2+b^2+c^2+d^2 = n이면서 각각 음수가 아니고 sqrt(n)보다 작은 a, b, c, d의 개수를 구한다.
또한 같은 숫자이면 부호가 같아야 한다는 조건도 있다.
DFS와 비슷한 느낌으로 접근했는데 부호에 신경을 써줘야 했다.
우선 a,b,c,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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
using P=pair<int,int>;
long long a, b, c, d;
long long ans = 0;
cin >> n;
vector<int> v;
for(int i=0;i*i<=n;i++){
v.push_back(i*i);
}
int sz=v.size()-1;
vector<int> z(4);
function <void(int, int, int)> back=[&](int cnt, int tt, int buho){
if(cnt==4){
if(tt==n){
//cout << z[0] << ' ' << z[1] << ' ' << z[2] << ' ' << z[3] << '\n';
ans++;
}
return;
}
if(cnt==0){
if(z[0]==0)return;
back(1, z[0], 1);
}
else{
if(z[cnt]==0){
back(4, tt, 1);
}
else if(z[cnt]==z[cnt-1]){ // 같으면
if(buho==1) back(cnt+1, tt+z[cnt], buho);
else back(cnt+1, tt-z[cnt], buho);
}
else{
back(cnt+1, tt+z[cnt], 1);
back(cnt+1, tt-z[cnt], -1);
}
}
};
for(int i1=sz;i1>=0;i1--){
for(int i2=i1;i2>=0;i2--){
for(int i3=i2;i3>=0;i3--){
for(int i4=i3;i4>=0;i4--){
z={v[i1], v[i2], v[i3], v[i4]};
back(0, 0, 0);
}
}
}
}
if(n==0)ans++;
cout << ans;
return 0;
}
D번 Pen Counts (3945, G4)
풀이
입력받은 총 길이로 만들 수 있는 삼각형의 개수를 세는 것이다.
가장 긴 변은 (n-1)/2, (n+2)/3으로 놓고, 그 다음 변은 가장 긴 변을 i라고 할 때
(n-i+1)/2, min(i, n-i-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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
using P=pair<int,int>;
long long a, b, c, d;
long long ans = 0;
cin >> t;
while(t-->0){
cin >> n;
ans=0;
// 가장 긴 애는 n/2보다 작아야함.
int a_r=(n-1)/2;
int a_l=(n+2)/3;
for(int i=a_r;i>=a_l;i--){
int b_l = (n-i+1)/2;
int b_r = min((ll)i, n-i-1);
for (int j=b_l;j<=b_r; j++) {
int c = n-i-j;
if(i==j&& j==c) ans+=1;
else if(i==j||j==c) ans+=1;
else ans+=2;
}
}
cout << ans << '\n';
}
return 0;
}
E번 연료가 부족해 (20293, G1)
풀이
처음에는 dp라고 생각했지만 범위가 작음에도 parametric search로 접근해야 하는 문제였다.
조건을 달성할 수 있는지를 bool 함수로 놓고 잘 짜주면 된다.
판별은 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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
using P=pair<int,int>;
using PP = pair<P,P>;
long long a, b, c, d;
long long ans = 0;
cin >> n >> m;
vector<vector<int>> v(n+1, vector<int>(m+1, 0)); //충전
cin >> t;
for(int i=0;i<t;i++){
cin >> a >> b >> c;
v[a][b]=c;
}
function <bool(int)> ok=[&](int x){
vector<vector<int>> dp(n+1, vector<int>(m+1, -1)); //여유분
dp[1][1]=x;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i==1 && j==1)continue;
dp[i][j]=max(dp[i-1][j], dp[i][j-1])-1;
if(dp[i][j]>=0) dp[i][j]+=v[i][j]; //이 경로로 갈 수 있는 조건
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout << dp[i][j] << ' ';
// }cout << '\n';
// }
if(dp[n][m]>=0)return true;
else return false;
};
int r=n+m-1;
int l=0;
while(l+1<r){
int mid=(l+r)>>1;
if(ok(mid)) r=mid;
else l=mid;
}
cout << r;
return 0;
}
F번 트리 정리하기 (23844, G1)
풀이
아이디어는 그리디로 밑에서부터 올라오며 K개를 선택하는데 자식이 많은 노드를 선택한다.
우선 트리를 만들고, depth가 가장 깊은 곳에서부터 priority_queue를 통해 노드를 저장해 풀었다.
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
107
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
using P=pair<int,int>;
using PP = pair<P,P>;
long long a, b, c, d;
long long ans = 0;
cin >> n >> m;
vector<vector<int>> graph(n+1);
vector<bool> chk(n+1, 0);
vector<vector<int>> tree(n+1);
for(int i=0;i<n-1;i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
int max_depth=0;
priority_queue<PP> pq; // depth랑 가중치, 좌표를 저장?
function<void(int, int)> dfs=[&](int x, int depth){
chk[x]=1;
for(int i=0;i<graph[x].size();i++){
if(!chk[graph[x][i]]){
max_depth=max(max_depth, depth);
tree[graph[x][i]].push_back(x);
pq.push({{depth, 1}, {graph[x][i], x}});
dfs(graph[x][i], depth+1);
}
}
};
chk[1]=1;
dfs(1, 1);
//max_depth가 젤 깊은 애
vector<int> wei(n+1, 1); //여기가 가중치를?
// for(int i=1;i<=n;i++){
// for(int j=0;j<tree[i].size();j++){
// cout << i << " : " << tree[i][j] << ' ';
// }cout << '\n';
// }
int kk = max_depth+1;
int gi=1e9;
int cnt=0;
vector<int> chk2(n+1, 0);
while(!pq.empty()){
int dd=pq.top().first.first;
int weight=pq.top().first.second;
int xx=pq.top().second.first;
int yy=pq.top().second.second;
if(chk2[xx]){
pq.pop();
continue;
}
if(gi<dd){
pq.pop();
continue;
}
if(weight<wei[xx]){
pq.pop();
pq.push({{dd, wei[xx]}, {xx, yy}});
continue;
}
if(kk>dd){
kk=dd;
cnt=1;
}
else{
cnt++;
}
//cout << yy << ' ' << xx << " : " << wei[yy] << ' ' << weight << '\n';
wei[yy]+=weight;
chk2[xx]=1;
if(yy!=1) pq.push({{dd-1, wei[yy]}, {yy, tree[yy][0]}});
// for(int i=1;i<=n;i++){
// cout << i << " : " << wei[i] << " | ";
// }cout<<"\n";
if(cnt==m){
gi=dd-1;
cnt=0;
//다음 depth로 넘어가야함.
}
pq.pop();
}
cout << wei[1];
return 0;
}
G번 Forbidden Turns (26106, P5)
풀이
변형 다익스트라 문제였다.
금지된 경로가 있고, 그곳을 지나지 않고 출발지에서 목적지까지 최소 경로로 간다.
아이디어는 DFS나 BFS에서 방향을 저장하며 chk 배열 만드는 것을 이용했다.
이전 경로가 어디였는지 priority_queue에 저장하고 금지된 경로를 확인한다.
경로를 저장할 때 숫자 범위가 커서 맵을 이용했더니 쉽게 구현할 수 있었다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
using P=pair<ll,ll>;
using PP = pair<P,P>;
long long a, b, c, d;
long long ans = 0;
cin >> n >> m >> t; //간선, 노드, 금지
int st, ed;
cin >> st >> ed;
vector<ll> dst(m, 1e16); //거리
dst[st]=0;
vector<map<P, ll>> ban(m);
priority_queue<pair<ll, P>> pq; //현재랑 위치랑 이전위치
vector<vector<P>> load(m);
vector<map<ll, ll>> chk(m);
for(int i=0;i<n;i++){
cin >> a >> b >> c;
load[a].push_back({b,c});
}
for(int i=0;i<t;i++){
cin >> a >> b >> c;
ban[a][{b,c}]=1;
}
pq.push({0, {st, -1}});
while(!pq.empty()){
ll val=pq.top().first*-1;
ll cur=pq.top().second.first;
ll pre=pq.top().second.second;
//cout << val << ' ' << cur << ' ' << pre << '\n';
pq.pop();
if(pre==-1){
for(int i=0;i<load[cur].size();i++){
ll to=load[cur][i].first;
ll dv=load[cur][i].second;
if(to==ed){
dst[to]=min(dst[to], val+dv);
continue;
}
dst[to]=val+dv;
pq.push({-1*dst[to],{to, cur}});
}
}
else{
for(int i=0;i<load[cur].size();i++){
ll to=load[cur][i].first;
ll dv=load[cur][i].second;
if(ban[pre][{cur, to}])continue;
if(to==ed){
dst[to]=min(dst[to], val+dv);
continue;
}
if(!chk[pre][to]){
chk[pre][to]=1;
dst[to]=val+dv;
pq.push({-1*dst[to],{to, cur}});
}
}
}
}
if(dst[ed]==1e16)cout<<"-1";
else cout << dst[ed];
return 0;
}
H번 Bad Wiring (5384, P5)
풀이
흔한 유형 중에 하나인 전구 버튼을 누르는 문제이다.
보통 그리디로 풀게 되는데 같은 버튼을 2번 누르면 안 누른 것과 같기 때문이다.
총 n개의 버튼이 있고, i번째 버튼을 눌렀을 때 i-m ~ i+m 번째의 전구가 바뀐다.
하지만 어떻게 접근해야할지 모르겠어서 editorial을 봤다.
아이디어는 처음부터 m개의 버튼을 누르는 모든 경우를 생각하면 된다는 것이다.
m은 최대 15이므로 15개의 버튼을 누르는 모든 케이스는 2^15개이고,
그 뒤부터는 누를 수 있는 버튼이 정해지게 된다.
m+1번째 버튼은 1번째 전구에 유일하게 영향을 미칠 수 있고, m+2번째는 2번째 전구..
m+k번째 버튼이 k번째 전구에 유일하게 영향을 미칠 수 있는 버튼이 되기 때문이다.
이제 브포 + greedy를 통해 가장 적은 버튼을 누르며 입력된 상태를 만드는 방법을 찾으면 된다.
xor 연산으로 값을 바꾸는거에 익숙하지 않아서 구현도 어려웠지만 해결 할 수 있었다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
using P=pair<ll,ll>;
using PP = pair<P,P>;
long long a, b, c, d;
long long ans = 1e9;
cin >> t;
while(t-->0){
cin >> n >> m;
flag=0;
ans=1e9;
vector<int> v(n+1);
for(int i=1;i<=n;i++)cin>>v[i];
auto press = [&](ll i, vector<int>& diff) {
int L=max(1LL, i-m);
int R=min(n, i+m);
diff[L]^=1;
if (R+1<=n+1) diff[R+1]^=1;
};
int tt = min(m, n);
int best = 1e9;
for (int mask=0;mask<(1<<tt);mask++) {
vector<int> diff(n+2, 0);
int cnt = 0;
bool ok = true;
for (int k=1; k<=tt; ++k) {
if (mask & (1 << (k-1))) {
press(k, diff);
cnt++;
}
}
int roll=0;
int last=n-m;
for (int i=1; i<=n; ++i) {
roll ^= diff[i];
int curr = v[i] ^ roll;
if (i<=last) {
if (curr==1) {
int p=i+m;
press(p, diff);
cnt++;
roll^=1;
}
} else {
if (curr == 1) {
ok = false;
break;
}
}
}
if (ok) best=min(best, cnt);
}
if (best==1e9) cout << "impossible\n";
else cout<<best<<'\n';
}
return 0;
}