백준 마라톤 (코스40)
(8/8)
39주차는 일본어 문제 + 위상 정렬 4문제라는 문제 셋을 받아서 풀 수 없었다..
그래도 이번 주차는 수학 + 애드 훅 구성으로 나와서 쉽게 풀만했다.
A번 노트북 세 대를 가지고 왔다 (33515, B5)
풀이
숫자 2개를 입력 받고 더 작은 것을 출력하면 되는 간단한 문제이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, k, t;
int o_1, o_2;
cin >> n >> m;
cout << min(n,m);
return 0;
}
B번 Itz Chess (Small) (12188, S1)
풀이
킹, 퀸, 룩, 비숍, 나이트, 폰의 좌표가 주어진다.
종류 상관없이 10개의 말이 있을 수 있고, 각각의 말이 잡을 수 있는 개수를 센다.
이 때 말을 잡는다고 사라지거나, 이동하는게 아니라 잡는 경우의 수를 세는 것이다.
완전 구현 + 문자열도 귀찮게 있는 문제이다. 심지어 푼 사람은 11명이라 저평가 되어있는 문제
각 말의 움직임을 다 구현해줘야 했다. 최대한 dx, dy로 줄여보려 했지만 깔끔하다고는 못하겠다.
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
108
109
110
111
112
113
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
vector<string> v;
// cin >> s >> n;
cin >> t;
a = 0;
int dx[8]={-1, -1, -1, 0, 1, 0, 1, 1};
int dy[8]={-1, 0, 1, -1, 1, 1, -1, 0};
while(t-->0){
a++;
long long cnt=0;
vector<vector<char>> board(10, vector<char>(10, 0));
cin >> m;
for(int i=0;i<m;i++){
string s;
cin >> s;
board[int(s[0]-'A'+1)][int(s[1]-'1'+1)] = s[3];
}
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
if(board[i][j]=='K'){
for(int k=0;k<8;k++){
if(board[i+dx[k]][j+dy[k]]>0)cnt++;
}
}
else if(board[i][j]=='P'){
if(board[i+1][j-1]>0)cnt++;
if(board[i+1][j+1]>0)cnt++;
}
else if(board[i][j]=='R'){
for(int k=1;k<8;k+=2){
int dd = 1;
while(1){
int nx = i + dx[k]*dd;
int ny = j + dy[k]*dd;
if(nx>0 && nx<=8 && ny>0 && ny<=8){
if(board[nx][ny]>0){
cnt++;
break;
}
}
else break;
dd++;
}
}
}
else if(board[i][j]=='Q'){
for(int k=0;k<8;k++){
int dd = 1;
while(1){
int nx = i + dx[k]*dd;
int ny = j + dy[k]*dd;
if(nx>0 && nx<=8 && ny>0 && ny<=8){
if(board[nx][ny]>0){
cnt++;
break;
}
}
else break;
dd++;
}
}
}
else if(board[i][j]=='B'){
for(int k=0;k<8;k+=2){
int dd = 1;
while(1){
int nx = i + dx[k]*dd;
int ny = j + dy[k]*dd;
if(nx>0 && nx<=8 && ny>0 && ny<=8){
if(board[nx][ny]>0){
cnt++;
break;
}
}
else break;
dd++;
}
}
}
else if(board[i][j]=='N'){
for(int k=0;k<8;k+=2){
int nx = i + dx[k]*2;
int ny = j + dy[k]*1;
if(nx>0 && nx<=8 && ny>0 && ny<=8){
if(board[nx][ny]>0){
cnt++;
}
}
nx = i + dx[k]*1;
ny = j + dy[k]*2;
if(nx>0 && nx<=8 && ny>0 && ny<=8){
if(board[nx][ny]>0){
cnt++;
}
}
}
}
}
}
cout << "Case #" << a << ": " << cnt << '\n';
}
return 0;
}
C번 트리를 간단하게 색칠하는 최소 비용 (25512, S1)
풀이
트리의 정점을 black이나 white로 칠한다. 이 때 맞닿은 점은 같은 색이면 안된다.
그러면 dfs로 내려갈 때 이전 것과 다르게 칠하면 되는 것이다.
결국 트리에서 높이가 같으면 색이 같고, 높이가 바뀔 때 색도 바뀐다.
그렇게 나눠준 다음 흑백흑백이 더 작은지 백흑백흑이 더 작은지 비교하면 된다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, k, t;
int o_1, o_2;
cin >> n;
vector<vector<int>> graph(n);
for(int i=0;i<n-1;i++){
cin >> a >> b;
graph[a].push_back(b);
}
vector<pair<int, int>> vp;
for(int i=0;i<n;i++){
cin >> a >> b;
vp.push_back({a,b});
}
vector<int> odd;
vector<int> even;
function <void(int, int)> dfs = [&](int k, int flag){
if(flag%2==0)odd.push_back(k);
else even.push_back(k);
for(int i=0;i<graph[k].size();i++){
dfs(graph[k][i], flag+1);
}
};
dfs(0,0);
long long bl = 0;
long long wh = 0;
for(int i=0;i<odd.size();i++){
bl += vp[odd[i]].first;
wh += vp[odd[i]].second;
}
for(int i=0;i<even.size();i++){
wh += vp[even[i]].first;
bl += vp[even[i]].second;
}
cout << min(wh, bl);
return 0;
}
D번 퇴사 2 (15486, G5)
풀이
처음에는 회의실 배정 문제랑 비슷하다고 생각했는데 조금 다른 것 같다.
상담 일에 걸리는 시간과, 보수가 주어진다.
그러면 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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
vector<string> v;
cin >> n;
vector<int> dp(n+1,0);
for(int i=1;i<=n;i++){
cin >> a >> b;
if(i+a-1 <= n && dp[i+a-1] < dp[i-1] + b){
dp[i+a-1]=dp[i-1] + b;
}
if(dp[i]<=dp[i-1])dp[i]=dp[i-1];
}
cout << dp[n];
return 0;
}
E번 종점 (22867, G5)
풀이
버스 도착과 떠나는 시간이 주어져서 최대 몇 개가 종점에 있는지 물어본다.
문자열이 HH:MM:SS.sss이라 파싱이 귀찮았다. 나중에 알고보니 그냥 문자열 비교로도 된다..
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, k, t;
int o_1, o_2;
string s1, s2;
long long l1, l2;
cin >> n;
vector<long long> dul;
vector<long long> na;
for(int i=0;i<n;i++){
cin >> s1;
l1 = int(s1[0]-48)*pow(10, 8) + int(s1[1]-48)*pow(10, 7) + int(s1[3]-48)*pow(10, 6) + int(s1[4]-48)*pow(10, 5)
+ int(s1[6]-48)*pow(10, 4) + int(s1[7]-48)*1000 + int(s1[9]-48)*100 + int(s1[10]-48)*10 + int(s1[11]-48);
cin >> s1;
l2 = int(s1[0]-48)*pow(10, 8) + int(s1[1]-48)*pow(10, 7) + int(s1[3]-48)*pow(10, 6) + int(s1[4]-48)*pow(10, 5)
+ int(s1[6]-48)*pow(10, 4) + int(s1[7]-48)*1000 + int(s1[9]-48)*100 + int(s1[10]-48)*10 + int(s1[11]-48);
dul.push_back(l1);
na.push_back(l2);
}
dul.push_back(1e16);
na.push_back(1e16);
sort(dul.begin(), dul.end());
sort(na.begin(), na.end());
int mx = -1;
int l=0, r=0;
while(1){
if(l==n && r==n)break;
if(dul[l]<na[r]){
l++;
}
else{
r++;
}
mx = max(mx, l-r);
}
cout << mx;
return 0;
}
F번 데이터 만들기 1 (7140, G4)
풀이
주어진 코드에서 반례를 만드는 문제라 처음에는 감을 못 잡았다.
코드를 좀 읽어보니 반례를 만드는 코드 시간 복잡도가 O(N^3)인 것이 뻔히 보여서
그것을 넘어가도록 예시를 만들어서 풀었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, k, t;
int o_1, o_2;
cout << 101 << '\n';
for(int i=0;i<101;i++){
cout << 0 << '\n';
}
cout << 1 << '\n';
cout << 0 << ' ' << 3 << '\n';
return 0;
}
G번 Construct Points (23483, G3)
풀이
점 네개의 좌표를 찍는데, 모든 x, y의 절댓값이 10^9보다 작거나 같다.
이 때 a,b를 지나는 직선과 c,d를 지나는 직선의 교점의 x,y좌표 절댓값이 10^27보다 크게 해야 한다.
계산을 해보니 기울기가 1인 직선과 1과 가장 가까운 직선을 그으면 10^27보다 교점이 커졌다.
그렇기에 아래처럼 값을 주면 된다.
1
2
3
4
0 -999999999
1000000000 0
-999999999 2
0 1000000000
H번 비밀의 레시피 (25922, G2)
풀이
인터랙티브 문제에 익숙해지고 있다.
코드포스도 슬슬 재활을 해야하는데 너무 귀찮네요..
보자마자 라그랑주 방정식이 떠올랐는데, 그렇게 푸는 것은 아닌 것 같다.
n차 다항식의 각 계수를 구하면 되는 문제이다.
값을 넘겨주면 그것을 x에 넣어 계산한 값을 반환해준다.
이 때 계수의 제한이 10^9이고, 입력이 가능한 크기는 2^31이다.
그러면 x에 10^9를 넣어주면 각 계수들이 그대로 나타나게 된다.
나머지는 반환받은 문자열을 9글자씩 파싱하면 그것이 계수이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, k, t;
int o_1, o_2;
cin >> n;
cout << "? 1000000000" << endl;
string s;
cin >> s;
cout << "\n! ";
for (int i = s.size(); i > 0; i -= 9) {
int start = max(i - 9, 0);
cout << stoi(s.substr(start, i - start)) << ' ';
}
cout << endl;
return 0;
}