대회/대회 출제 후기

[BOJ 21734 - 21740] SMUPC 대회 문제 풀이

whaeun 2021. 5. 30. 12:38

 

A. SMUPC의 등장 [BOJ 21734] - https://www.acmicpc.net/problem/21734

 

21734번: SMUPC의 등장

2021년 5월 8일 SMUPC 대회의 첫 개최에 신이 난 화은이는 SMUPC를 기념하기 위해 "SMUPC"를 예술적으로 출력하는 프로그램을 작성하고자 했다. 화은이는 각 알파벳에 해당하는 아스키코드 값을 10진

www.acmicpc.net

 

SMUPC의 등장은 단순 구현 문제로 입력으로 주어지는 문자열의 각 문자에 대해 아스키코드의 각자리 숫자의 합만큼 반복해서 출력하면 되는 문제였다.

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
#include<iostream>
#include<string>
 
using namespace std;
 
int calculate(char c) {
    int a = (int)c;
    a = a / 100 + a / 10 - a / 100  * 10 + a % 10;
    return a;
}
 
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    string s;
    cin >> s;
    
    for (int i = 0; i < s.length(); i++) {
        int num = calculate(s[i]);
        for (int j = 0; j < num; j++) {
            cout << s[i];
        }
        cout << "\n";
    }
}
 cs

B. 눈덩이 굴리기 [BOJ 21735] - https://www.acmicpc.net/problem/21735

 

21735번: 눈덩이 굴리기

눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은

www.acmicpc.net

 

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int snow[101];
int snowball[101][11] = {0, };
 
int main() {
    ios::sync_with_stdio(false); 
    cout.tie(NULL); 
    cin.tie(NULL);
 
    int n, m, answer = 0;
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        cin >> snow[i];
    }
 
    snowball[0][0] = 1;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i < j || i / 2 + i % 2   >  j) {
                continue;
            }
            snowball[i][j] = max(snowball[i][j], snowball[i - 1][j - 1] + snow[i]);
            if (i+2 <= n) {
                snowball[i + 2][j + 1] = snowball[i][j] / 2 + snow[i + 2];
            }
            answer = max(snowball[i][j], answer);
        }
    }
    cout << answer;
}
 cs

 

C. 헌내기는 친구가 필요해 [BOJ 21736] - https://www.acmicpc.net/problem/21736

 

21736번: 헌내기는 친구가 필요해

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고

www.acmicpc.net

 

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int n, m, people = 0;
 
vector < vector <char> > v;
vector <char> v2;
 
vector <vector<int>> visited;
vector<int> v3;
 
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
 
void bfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int a, b;
 
        a = x + dx[i];
        b = y + dy[i];
        if (a >= 0 && b >= 0 && a < m && b < n && !visited[b][a] && v[b][a] != 'X') {
            visited[b][a] = 1;
            if (v[b][a] == 'P') {
                people++;
            }
            bfs(a, b);
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false); 
    cout.tie(NULL); 
    cin.tie(NULL);
    
    int x, y;
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        v.push_back(v2);
        visited.push_back(v3);
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char a;
 
            cin >> a;
 
            if (a == 'I') {
                y = i;
                x = j;
            }
 
            visited[i].push_back(0);
            v[i].push_back(a);
        }
    }
 
    bfs(x, y);
 
    if (people == 0) {
        cout << "TT";
    }
    else {
        cout << people;
    }
 
}
 cs

D. SMUPC 계산기 [BOJ 21737] - https://www.acmicpc.net/problem/21737

 

21737번: SMUPC 계산기

SMUPC를 기념하기 위해 ALGOS와 DSC Sookmyung에서는 SMUPC의 각 글자로 계산이 이루어지는 계산기를 만들었다. 가은이와 혜민이는 이 계산기와 같은 방식으로 작동하는 프로그램을 만들고자 한다. 가은

www.acmicpc.net

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
#include<iostream>
#include<string>
 
using namespace std;
 
int result = 0;
 
void calculate(char op, int a) {
    switch (op) {
    case 'S':
        result -= a;
        break;
    case 'M':
        result *= a;
        break;
    case 'U':
        result /= a;
        break;
    case 'P':
        result += a;
        break;
    }
}
 
int main() {
    int n, a = 0;
    int count = 0;
    char op;
    cin >> n;
    char c = getchar();
    c = getchar();
    while (!(c == 'S' || c == 'M' || c == 'U' || c == 'P' || c == 'C')) {
        result = result * 10 + (c - '0');
        c = getchar();
    }
    op = c;
    while (n > 0) {
        if (op == 'C') {
            count++;
            n--;
            cout << result << " ";
            c = getchar();
            op = c;
        }
        else {
            n--;
            if (n == 0) {
                break;
            }
            c = getchar();
            a = 0;
            while (!(c == 'S' || c == 'M' || c == 'U' || c == 'P' || c == 'C')) {
                a = a * 10 + (c - '0');
                c = getchar();
            }
            calculate(op, a);
            op = c;
 
        }
    }
    if (count == 0) {
        cout << "NO OUTPUT";
    }
}
 cs

E. 얼음깨기 펭귄 [BOJ 21738] - https://www.acmicpc.net/problem/21738

 

21738번: 얼음깨기 펭귄

첫째 줄에 얼음 블록의 개수 $N$($ 3 \leq N \leq 328\,000$)과 지지대의 역할을 하게 되는 얼음의 개수 $S$($ 2 \leq S \leq N-1$), 펭귄이 위치한 얼음 블록의 번호 $P$($ S \lt P \leq N$)가 주어진다. 지지대의 역

www.acmicpc.net

[BFS 풀이]

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int n, s, p;
 
vector<vector<int>> edge;
vector<int> v;
vector<int> visited;
queue<int> q;
 
int bfs(int node){
    q.push(-1);
    q.push(node);
    visited[node] = 1;
    
    int now, degree = -1, count = 0, answer = 0;
    
    while(!q.empty()){
        now = q.front();
        q.pop();
        
        if(now == -1){
            degree++;
            q.push(-1);
            continue;
        }
        
        if(now <=s){
            count++;
            answer += degree;
            if(count == 2){
                break;
            }
        }
        for(int i = 0; i < edge[now].size(); i++){
            if(!visited[edge[now][i]]){
                q.push(edge[now][i]);
                visited[edge[now][i]] = 1;
            }
        }  
    }
    return answer;
}
 
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
 
    cin >> n >> s >> p;
 
    edge.push_back(v);
    visited.push_back(0);
 
    for (int i = 1; i <= n; i++) {
        edge.push_back(v);
        visited.push_back(0);
    }
 
    for (int j = 1; j < n; j++) {
        int a, b;
 
        cin >> a >> b;
 
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
 
    cout << n - bfs(p) - 1;
}
 cs

[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
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int n, s, p;
 
vector<vector<int>> edge;
vector<int>answer;
vector<int> v;
 
void dfs(int node, int parent, int degree) {
 
    for (int i = 0; i < edge[node].size(); i++) {
        if (edge[node][i] == p) {
            answer.push_back(degree);
            return;
        }
 
        if (edge[node][i] == parent) {
            continue;
        }
 
        dfs(edge[node][i], node, degree + 1);
 
    }
}
 
int main() {
    ios::sync_with_stdio(false); 
    cout.tie(NULL); 
    cin.tie(NULL);
 
    cin >> n >> s >> p;
 
    edge.push_back(v);
 
    for (int i = 1; i <= n; i++) {
        edge.push_back(v);
    }
 
    for (int j = 1; j < n; j++) {
        int a, b;
 
        cin >> a >> b;
 
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
 
    for (int i = 1; i <= s; i++) {
        dfs(i, -1, 1);
    }
 
    sort(answer.begin(), answer.end());
 
    cout << n - (answer[0] + answer[1]) - 1;
}
 cs

F. 펭귄 네비게이터 [BOJ 21739] - https://www.acmicpc.net/problem/21739

 

21739번: 펭귄 네비게이터

펭귄은 현재 ($1$, $1$)에 있다. 펭귄은 집까지 가고 싶다. 펭귄의 집은 ($2$, $N$)이다. 하지만 누군가에 의해 얼음길이 다 깨져 집에 갈 수 없게 되었다. 현진이는 펭귄들을 위해 얼음길을 만들어줄

www.acmicpc.net

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
#include<iostream>
 
#define MOD 1000000007
 
using namespace std;
 
long long func(long long a, long long b) {
    long long result = 1;
 
    while (b > 0){
        if (b % 2 == 1) {
            result = result * a % MOD;
        }
 
        a = a * a % MOD;
        b /= 2;
    }
 
    return result;
}
 
int main() {
    ios::sync_with_stdio(false); 
    cout.tie(NULL); 
    cin.tie(NULL);
 
    int n;
    long long n1 = 1, n2 = 1, n3;
    long long answer;
 
    cin >> n;
 
    if (n == 1) {
        cout << 1;
        return 0;
    }
 
    for (int i = 2; i <= 2 * n; i++) {
        n1 = n1 * i % MOD;
    }
 
    for (int i = 2; i <= n+1; i++) {
        n2 = n2 * i % MOD;
        if (i == n) {
            n3 = n2;
        }
    }
 
    answer = func(n3, MOD - 2) % MOD;
    answer = answer * (func(n2, MOD - 2) % MOD) % MOD;
 
    answer = answer * n1 % MOD;
 
    cout << answer;
 
}
 cs

G. 도도의 수학놀이 [BOJ 21740] - https://www.acmicpc.net/problem/21740

 

21740번: 도도의 수학놀이

길이가 N인 수열이 주어진다. 도도는 이 수열의 수를 이어붙여 180도 회전시켰을 때 가장 큰 수를 만들려고 한다. 각 숫자를 180도 회전시켰을 때 환원되는 숫자는 다음과 같다. $0$ -> $0$ $1$ -> $1$ $2$

www.acmicpc.net

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
vector<pair<int, int>> dodo;
 
int rotate_number(int num){
    switch(num){
        case 6:
            return 9;
            break;
        case 9:
            return 6;
            break;
        default:
            return num;
    }
}
 
int int_size(int num){
    int count = 0;
    for(count = 0; num > 0; count++){
        num /= 10;
    }
    return count;
}
 
int reverse_num(int num){
    int result = 0;
    
    int num_size = int_size(num);
    for(int i =0; i < num_size; i++){
        result = result * 10 + rotate_number(num % 10);
        num /= 10;
    }
    
    return result;
}
 
bool cmp(const pair<int, int> & a, const pair<int, int> & b){
    long long sum1 = 0, sum2 = 0;
    
    sum1 = a.first * pow(10, int_size(b.second)) + b.first;
    sum2 = b.first * pow(10, int_size(a.second)) + a.first;
    
    return sum1 < sum2;
}
 
int main(){
    int n, max_num = 0;
    int max_num_origin = 0;
    
    cin >> n;
    
    for(int i =0; i<n; i++){
        int a, reverse_a;
        
        cin >> a;
        
        reverse_a = reverse_num(a);
        
        if((max_num < reverse_a && int_size(max_num_origin) <= int_size(a))  || int_size(max_num_origin) < int_size(a)){
            max_num = reverse_a;
            max_num_origin = a;
        }
        
        dodo.push_back(make_pair(reverse_a, a));
    }
    
    dodo.push_back(make_pair(max_num, max_num_origin));
    
    sort(dodo.begin(), dodo.end(), cmp);
    
    for(int i =0; i<=n; i++){
        cout << dodo[i].second;
    }
}
 cs

 

- 문제 풀이 슬라이드:

https://upload.acmicpc.net/b12b2c1c-f37f-4d44-a2b6-fe20ce02655e/

 

[ 추천 문제 ]

- 독특한 계산기 [BOJ 19591] - https://www.acmicpc.net/problem/19591

- 큰 수 만들기 [BOJ 16496] - https://www.acmicpc.net/problem/16496

 

 

저작자표시 비영리 (새창열림)