반응형

https://www.acmicpc.net/problem/13544

 

13544번: 수열과 쿼리 3

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/462

 

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)

1. 머지 소트 트리(Merge Sort Tree) 머지 소트 트리(Merge Sort Tree)는 분할 정복을 활용하는 합병 정렬(Merge Sort)을 저장하는 자료구조 입니다. 2. 머지 소트 트리(Merge Sort Tree) 동작 원리 머지 소트 트리(Me

rudalsd.tistory.com

 

1. 수열을 입력받고, 머지 소트 트리를 구현합니다.

 

2. a, b, c를 입력받고 pre에 xor 한 후 그 값을 이용하여 해당 구간에 대해 upper_bound를 활용하여, 해당 구간의 값 중 k보다 큰 값을 ans에 저장합니다.

 

3. ans를 출력하고, pre에 ans를 저장한 후 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
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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> mergeSortTree[262222];
int arr[100001];
int ans;
int pre;
 
void merge(int node, int s, int e)
{
    int s_size = mergeSortTree[node * 2].size();
    int e_size = mergeSortTree[node * 2 + 1].size();
    int i = 0, j = 0;
 
    while (1) {
        if (mergeSortTree[node * 2][i] < mergeSortTree[node * 2 + 1][j]) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i++]);
        }
        else {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j++]);
        }
 
        if (i == s_size || j == e_size) {
            break;
        }
    }
 
    if (i < s_size) {
        for (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
    else {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        mergeSortTree[node].push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    merge(node, s, e);
}
 
void getTree(int node, int s, int e, int i, int j, int k)
{
    if (s > j || e < i) return;
    if (i <= s && e <= j) {
        ans += mergeSortTree[node].end() - upper_bound(mergeSortTree[node].begin(), mergeSortTree[node].end(), k);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, i, j, k);
    getTree(node * 2 + 1, m + 1, e, i, j, k);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    cin >> M;
 
    while (M--) {
        int a, b, c;
        cin >> a >> b >> c;
 
        ans = 0;
 
        a ^= pre;
        b ^= pre;
        c ^= pre;
 
        getTree(1, 1, N, a, b, c);
 
        cout << ans << '\n';
 
        pre = ans;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14
[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13
반응형

https://www.acmicpc.net/problem/5069

 

5069번: 미로에 갇힌 상근

상근이는 오른쪽 그림과 같은 미로에 갇혀있다. 미로는 육각형 모양의 방이 계속해서 붙어있는 모양이고, 이러한 방은 무수히 많이 있다. 또, 인접한 방은 문으로 연결되어 있어서, 한 방에서 다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[ 30 ][ 30 ][ 15 ]를 선언하고 -1로 초기화해 줍니다.

 

2. 6방향으로 이동하면서 이동 가능 거리가 0이 남았을 때 출발한 위치라면 1을 return 합니다.

 

3. dp[ 10 ][ 10 ][ n ]을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int dp[30][30][15];
int dy[] = { -1,0,1,1,0,-1 };
int dx[] = { 0,1,1,0,-1,-1 };
int T, n;
 
int dfs(int y, int x, int cnt)
{
    if (dp[y][x][cnt] != -1) return dp[y][x][cnt];
    if (cnt == 0) return y == 10 && x == 10;
    int& ret = dp[y][x][cnt];
    ret = 0;
 
    for (int i = 0; i < 6; i++) {
        const int yy = y + dy[i];
        const int xx = x + dx[i];
        if (yy >= 0 && yy < 30 && xx >= 0 && xx < 30) {
            ret += dfs(yy, xx, cnt - 1);
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int i = 0; i < 30; i++) {
        for (int j = 0; j < 30; j++) {
            for (int k = 0; k <= 14; k++) {
                dp[i][j][k] = -1;
            }
        }
    }
 
    while (T--) {
        cin >> n;
 
        cout << dfs(10, 10, n) << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
[ 백준 ] 13544번 - 수열과 쿼리 3 (C++)  (0) 2023.10.16
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14
[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13
[ 백준 ] 19942번 - 다이어트 (C++)  (0) 2023.10.12
반응형

https://www.acmicpc.net/problem/1737

 

1737번: Pibonacci

첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[ 1001 ][ 320 ]을 선언하고 -1로 초기화해 줍니다.

 

2. P[ i ] = P[ i - 1 ] + P[ i - π * j ]를 통해 dp[ i ][ j ]를 기록해 줍니다.

 

3. 재귀함수를 통해 i - π * j가 0보다 크거나 같고, π보다 작거나 같을 때 1을 return 해줍니다.

 

4. dp[ n ][ 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
#define _USE_MATH_DEFINES
#include<iostream>
#include<cmath>
#define ll long long
#define M 1000000000000000000
 
using namespace std;
 
int n;
ll dp[1001][320];
 
ll dfs(int i, int j)
{
    if (dp[i][j] != -1) return dp[i][j];
    if (i - M_PI * j >= 0 && i - M_PI * j <= M_PI) return 1;
    return dp[i][j] = (dfs(i - 1, j) % M + dfs(i, j + 1) % M) % M;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 319; j++) {
            dp[i][j] = -1;
        }
    }
 
    cout << dfs(n, 0);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 13544번 - 수열과 쿼리 3 (C++)  (0) 2023.10.16
[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13
[ 백준 ] 19942번 - 다이어트 (C++)  (0) 2023.10.12
[ 백준 ] 21276번 - 계보 복원가 호석 (C++)  (0) 2023.10.11
반응형

https://www.acmicpc.net/problem/25498

 

25498번: 핸들 뭘로 하지

효규가 얻을 수 있는 문자열은 사전순으로 "$\text{aa}$", "$\text{aaa}$", "$\text{aaaa}$", "$\text{aaaa}$"이므로 "$\text{aaaa}$"를 핸들로 정한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열과 그래프를 입력받고, arr[500001]과 vector<int> list[500001]에 저장합니다.

 

2. node struct를 만들어 현재 노드의 번호, 인덱스 그리고 부모의 문자를 저장합니다.

 

3. queue<node> q를 만들어 bfs를 돌면서 해당 인덱스에서 가장 큰 문자를 ans에 더해주면서 문자열을 완성합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
#include<string>
 
using namespace std;
 
struct node {
    int cur, idx;
    char parent;
};
 
int N;
char arr[500001];
vector<int> list[500001];
int visited[500001];
string ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> arr;
 
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    queue<node> q;
    q.push({ 1, 1, '0'});
    visited[1] = 1;
    ans += '0';
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int idx = q.front().idx;
        const char pa = q.front().parent;
        q.pop();
 
        if (pa != ans[idx - 1]) continue;
        if (idx >= ans.size()) ans += arr[cur - 1];
        else if (ans[idx] < arr[cur - 1]) {
            ans[idx] = arr[cur - 1];
        }
 
        for (auto& next : list[cur]) {
            if (visited[next] != 1) {
                visited[next] = 1;
                q.push({ next,idx + 1, arr[cur - 1]});
            }
        }
    }
 
    ans.erase(ans.begin());
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14
[ 백준 ] 19942번 - 다이어트 (C++)  (0) 2023.10.12
[ 백준 ] 21276번 - 계보 복원가 호석 (C++)  (0) 2023.10.11
[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
반응형

https://www.acmicpc.net/problem/19942

 

19942번: 다이어트

식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N을 입력받고, 백트래킹을 이용해 식재료를 선택하고 영양성분을 만족하고, 최소 비용이 든다면 ans에 식재료의 집합을 저장합니다.

 

2. 영양성분을 만족하지 못한다면 -1을 출력하고, 그렇지 않다면 비용과 ans 집합을 출력합니다.

 

[ 소스코드 ]

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;
 
struct food {
    int p, f, s, v, c;
};
 
int N;
int mp, mf, ms, mv;
food arr[15];
int cost = 987654321;
int tmp[5];
vector<int> ans;
vector<int> bucket;
 
void dfs(int level, int n)
{
    if (tmp[0] >= mp && tmp[1] >= mf && tmp[2] >= ms && tmp[3] >= mv) {
        if (cost > tmp[4]) {
            cost = tmp[4];
            ans = bucket;
        }
        return;
    }
    if (level == N) {
        return;
    }
 
    for (int i = n; i < N; i++) {
        tmp[0] += arr[i].p;
        tmp[1] += arr[i].f;
        tmp[2] += arr[i].s;
        tmp[3] += arr[i].v;
        tmp[4] += arr[i].c;
        bucket.push_back(i);
        dfs(level + 1, i + 1);
        tmp[0] -= arr[i].p;
        tmp[1] -= arr[i].f;
        tmp[2] -= arr[i].s;
        tmp[3] -= arr[i].v;
        tmp[4] -= arr[i].c;
        bucket.erase(bucket.end() - 1);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> mp >> mf >> ms >> mv;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i].p >> arr[i].f >> arr[i].s >> arr[i].v >> arr[i].c;
    }
 
    dfs(0, 0);
 
    if (cost == 987654321) {
        cout << -1;
        return 0;
    }
 
    cout << cost << '\n';
 
    for (auto& next : ans) {
        cout << next + 1 << ' ';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14
[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13
[ 백준 ] 21276번 - 계보 복원가 호석 (C++)  (0) 2023.10.11
[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
[ 백준 ] 3780번 - 네트워크 연결 (C++)  (0) 2023.10.09
반응형

https://www.acmicpc.net/problem/21276

 

21276번: 계보 복원가 호석

석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/72

 

[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방

rudalsd.tistory.com

 

1. 조상으로부터 자손으로 이어지는 단방향 그래프를 list 배열에 저장합니다.

 

2. 1과 동시에 조상의 개수를 cnt[ i ]++를 통해 저장해 주고, cnt[ i ]가 0이면 queue에 넣어줍니다.

 

3. queue를 돌면서 cnt[ i ]가 0일 때 queue에 해당 자손을 넣어주고, 그때의 조상이 직계 조상이므로 child 배열에 해당 자손을 넣어줍니다.

 

4. 가장 초기에 cnt[ i ]가 0인 조상은 가문의 시조이므로 parent 배열에 넣어줍니다.

 

5. 조건에 맞게 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
 
using namespace std;
 
int N, M;
map<string, int> m;
string str[1000];
int cnt[1000];
map<string, vector<string>> child;
vector<int> list[1000];
vector<string> parent;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> str[i];
        m[str[i]] = i;
    }
 
    cin >> M;
 
    for (int i = 0; i < M; i++) {
        string tmp[2];
        cin >> tmp[0] >> tmp[1];
        cnt[m[tmp[0]]]++;
        list[m[tmp[1]]].push_back(m[tmp[0]]);
    }
 
    queue<int> q;
 
    for (int i = 0; i < N; i++) {
        if (cnt[i] == 0) {
            q.push(i);
            parent.push_back(str[i]);
        }
    }
 
    while (!q.empty()) {
        const int cur = q.front();
        q.pop();
 
        for (auto& next : list[cur]) {
            cnt[next]--;
            if (cnt[next] == 0) {
                child[str[cur]].push_back(str[next]);
                q.push(next);
            }
        }
    }
 
    sort(parent.begin(), parent.end());
 
    cout << parent.size() << '\n';
 
    for (auto& next : parent) {
        cout << next << ' ';
    }
 
    cout << '\n';
 
    sort(str, str + N);
 
    for (int i = 0; i < N; i++) {
        cout << str[i] << ' ' << child[str[i]].size() << ' ';
        sort(child[str[i]].begin(), child[str[i]].end());
        for (auto& next : child[str[i]]) {
            cout << next << ' ';
        }
        cout << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13
[ 백준 ] 19942번 - 다이어트 (C++)  (0) 2023.10.12
[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
[ 백준 ] 3780번 - 네트워크 연결 (C++)  (0) 2023.10.09
[ 백준 ] 20210번 - 파일 탐색기 (C++)  (1) 2023.10.08
반응형

https://www.acmicpc.net/problem/17085

 

17085번: 십자가 2개 놓기

첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N, M을 입력받고, 격자판을 입력받습니다.

 

2. 십자가의 최대 크기가 7이므로 두 개의 십자가 크기가 7, 7부터 0, 0까지 격자판에 놓고, 두 십자가의 넓이의 곱의 최댓값을 ans에 저장합니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
char arr[15][16];
int temp[15][15];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
bool flag = false;
int visited[15][15];
int ans;
 
bool check(int y, int x, int n)
{
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= n; j++) {
            int yy = y + dy[i] * j;
            int xx = x + dx[i] * j;
 
            if (arr[yy][xx] == '#' && visited[yy][xx] != 1) {
                visited[yy][xx] = 1;
            }
            else {
                return false;
            }
        }
    }
 
    return true;
}
 
void dfs(int a, int b, int cnt)
{
    if (flag) return;
    if (cnt == 2) {
        ans = max(ans, (1 + 4 * a) * (1 + 4 * b));
        flag = true;
        return;
    }
 
    int tmp;
 
    if (cnt == 0) tmp = a;
    else tmp = b;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            temp[i][j] = visited[i][j];
        }
    }
 
    for (int i = tmp; i < N - tmp; i++) {
        for (int j = tmp; j < M - tmp; j++) {
            if (arr[i][j] == '#' && visited[i][j] != 1) {
                visited[i][j] = 1;
                if (check(i, j, tmp)) {
                    dfs(a, b, cnt + 1);
                }
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        visited[i][j] = temp[i][j];
                    }
                }
            }
        }
    }
 
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 7; i >= 0; i--) {
        for (int j = i; j >= 0; j--) {
            flag = false;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    visited[i][j] = 0;
                }
            }
            dfs(i, j, 0);
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 19942번 - 다이어트 (C++)  (0) 2023.10.12
[ 백준 ] 21276번 - 계보 복원가 호석 (C++)  (0) 2023.10.11
[ 백준 ] 3780번 - 네트워크 연결 (C++)  (0) 2023.10.09
[ 백준 ] 20210번 - 파일 탐색기 (C++)  (1) 2023.10.08
[ 백준 ] 20120번 - 호반우와 리듬게임 (C++)  (1) 2023.10.07
반응형

https://www.acmicpc.net/problem/3780

 

3780번: 네트워크 연결

입력은 여러 개의 테스트케이스로 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스에는 기업의 수를 나타내는 N(4 ≤ N ≤ 20,000)이 주어진다. 다음은 몇

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언하고, vect[ i ] = i로 초기화합니다.

 

2. I 커맨드를 입력 받을 때마다 I와 J를 연결해 주고, dist[ I ] = abs(I - J) % 1000으로 갱신해 줍니다.

 

3. E 커맨드를 입력받을 때마다 Find 함수를 통해 부모 노드를 찾아주고, 각 노드에서 부모 노드까지의 거리를 dist[ num ] 에 저장해 줍니다.

 

4. dist[ I ]를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int T, N;
int vect[20001];
int dist[20001];
 
pair<int,int> Find(int num)
{
    if (vect[num] == num) return make_pair(num, dist[num]);
    pair<int,int> temp = Find(vect[num]);
    vect[num] = temp.first;
    dist[num] += temp.second;
    return make_pair(vect[num], dist[num]);
}
 
void Union(int I, int J)
{
    vect[I] = J;
    dist[I] = abs(J - I) % 1000;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> N;
 
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
            dist[i] = 0;
        }
 
        while (1) {
            char cmd;
            cin >> cmd;
 
            if (cmd == 'E') {
                int I;
                cin >> I;
                Find(I);
 
                cout << dist[I] << '\n';
            }
            else if (cmd == 'I') {
                int I, J;
                cin >> I >> J;
 
                Union(I, J);
            }
            else break;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 21276번 - 계보 복원가 호석 (C++)  (0) 2023.10.11
[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
[ 백준 ] 20210번 - 파일 탐색기 (C++)  (1) 2023.10.08
[ 백준 ] 20120번 - 호반우와 리듬게임 (C++)  (1) 2023.10.07
[ 백준 ] 17299번 - 오등큰수 (C++)  (1) 2023.10.06
반응형

https://www.acmicpc.net/problem/20210

 

20210번: 파일 탐색기

첫 줄에 문자열의 개수 N(2 ≤ N ≤ 10,000)이 주어진다. 그 다음 N줄에 정렬할 문자열이 한 줄에 하나씩 주어진다. 모든 문자열의 길이는 100 이하이며, 알파벳 대소문자와 숫자로만 이루어져 있다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열을 입력받고, arr 배열에 저장합니다.

 

2. cmp 함수를 만들어 문자열을 서로 비교하면서 두 문자열이 모두 숫자가 나온다면 0이 아닌 숫자가 나온 시점부터 string에 넣어줍니다.

 

3. 두 숫자가 같을 때 사이즈가 다르면 사이즈가 더 작은 수를 앞에 두고, 사이즈가 같다면 각 자리 숫자를 비교해 주면서 더 작은 숫자를 앞에 둡니다.

 

4. cmp함수를 통해 arr 배열을 정렬해주고, arr배열을 출력해 줍니다.

 

[ 소스코드 ]

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
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<string>
#include<algorithm>
 
using namespace std;
 
int N;
string arr[10000];
 
bool cmp(string left, string right)
{
    if (left == right) return false;
 
    int l = 0, r = 0;
    while (1) {
        if (l == left.size()) {
            return true;
        }
        if (r == right.size()) {
            return false;
        }
 
        if (left[l] <= '9' && right[r] <= '9') {
            int sizeL = 0, sizeR = 0;
            string L, R;
            bool zeroL = false, zeroR = false;
            while (left[l] <= '9' && l < left.size()) {
                if (left[l] != '0' && zeroL == false) {
                    zeroL = true;
                }
                
                if (zeroL) {
                    L += left[l];
                }
 
                l++;
                sizeL++;
            }
 
            while (right[r] <= '9' && r < right.size()) {
                if (right[r] != '0' && zeroR == false) {
                    zeroR = true;
                }
 
                if (zeroR) {
                    R += right[r];
                }
                r++;
                sizeR++;
            }
 
            if (R == L) {
                if (sizeL != sizeR) {
                    return sizeL < sizeR;
                }
            }
            else {
                if (L.size() == R.size()) {
                    for (int i = 0; i < L.size(); i++) {
                        if (L[i] != R[i]) {
                            return L[i] < R[i];
                        }
                    }
                }
                return L.size() < R.size();
            }
            continue;
        }
        
        if (left[l] != right[r]) {
            if (left[l] >= 'a') {
                if (right[r] >= 'a') {
                    return left[l] < right[r];
                }
                else if (right[r] >= 'A') {
                    return left[l] - 'a' < right[r] - 'A';
                }
                else {
                    return false;
                }
            }
            else if (left[l] >= 'A') {
                if (right[r] >= 'a') {
                    return left[l] - 'A' <= right[r] - 'a';
                }
                else if (right[r] >= 'A') {
                    return left[l] < right[r];
                }
                else {
                    return false;
                }
            }
            else {
                if (right[r] >= 'A') {
                    return true;
                }
            }
        }
 
        l++;
        r++;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + N, cmp);
 
    for (int i = 0; i < N; i++) {
        cout << arr[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
[ 백준 ] 3780번 - 네트워크 연결 (C++)  (0) 2023.10.09
[ 백준 ] 20120번 - 호반우와 리듬게임 (C++)  (1) 2023.10.07
[ 백준 ] 17299번 - 오등큰수 (C++)  (1) 2023.10.06
[ 백준 ] 2186번 - 문자판 (C++)  (1) 2023.10.05
반응형

https://www.acmicpc.net/problem/20120

 

20120번: 호반우와 리듬게임

호반우가 모든 노트를 처리하면 3×1 + 4×2 + (-7)×3 + 1×4 = -6 점을 얻을 수 있습니다. 3번 노트를 제외한 모든 노트를 처리하면 3×1 + 4×2 + 1×1 = 12 점을 얻을 수 있습니다. 3번 노트를 놓쳤기에 4번 노

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[ N ]을 선언하고 dp[0] = 0, dp[1]은 첫 번째 수로 초기화 해줍니다. 이때, N은 콤보를 의미합니다.

 

2. i = 1 부터 i < N까지 수를 탐색하면서 j = i부터 j >= 1까지 콤보 값을 다음과 같은 점화식으로 갱신합니다.

tmp = max(tmp, dp[j]);
dp[j + 1] = dp[j] + 1LL * t * (j + 1);

dp[0] = max(n[1], n[2]);
dp[1] = dp[0] + t;
n[2] = n[1];
n[1] = tmp;

 

3. n[ 1 ], n[ 2 ], dp[ 1 ] ~ dp[ N ] 까지의 값 중 가장 큰 값을 ans에 저장합니다.

 

4. ans가 0보다 작다면 0을 아니라면 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
ll dp[1001];
ll n[3];
ll ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
    cin >> dp[1];
    n[2] = n[1] = 0;
 
    for (int i = 1; i < N; i++) {
        int t;
        cin >> t;
        ll tmp = -5005000001;
        for (int j = i; j >= 1; j--) {
            tmp = max(tmp, dp[j]);
            dp[j + 1] = dp[j] + 1LL * t * (j + 1);
        }
        dp[0] = max(n[1], n[2]);
        dp[1] = dp[0] + t;
        n[2] = n[1];
        n[1] = tmp;
    }
    
    ans = max(n[1], n[2]);
 
    for (int i = 1; i <= N; i++) {
        ans = max(ans, dp[i]);
    }
 
    if (ans < 0) cout << 0;
    else cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3780번 - 네트워크 연결 (C++)  (0) 2023.10.09
[ 백준 ] 20210번 - 파일 탐색기 (C++)  (1) 2023.10.08
[ 백준 ] 17299번 - 오등큰수 (C++)  (1) 2023.10.06
[ 백준 ] 2186번 - 문자판 (C++)  (1) 2023.10.05
[ 백준 ] 2661번 - 좋은수열 (C++)  (1) 2023.10.04

+ Recent posts

티스토리툴바