반응형

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

 

11058번: 크리보드

N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr[ N ] 배열을 선언하고, 1부터 6까지  arr[ i ] = i로 초기화해 줍니다.

 

2. 다음과 같은 점화식을 세워 값을 갱신합니다.

arr[ i ] = max( arr[ i - 3 ] * 2, arr[ i - 4 ] * 3, arr[ i - 5 ] * 4 )

 

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

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

[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
반응형

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

 

2758번: 로또

선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[ n ][ m ] 배열을 선언하고 -1로 초기화해줍니다.

 

2. n번 째 로또 번호가 m일 때의 개수를 dp 배열에 저장합니다.

 

3. 로또 번호가 m을 넘어서면 안 되므로 m의 값을 top - down을 통해 바꿔가면서 dp의 값을 초기화합니다.

 

4. 매 테스트케이스마다 m의 값을 1부터 m까지 for문을 통해 돌면서 dfs( n, m )의 값을 모두 더해 출력합니다.

 

[ 소스코드 ]

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>
#include<cmath>
#define ll long long
 
using namespace std;
 
int T, n, m;
ll dp[11][2001];
 
ll dfs(int n, int m)
{
    if (n == 1) {
        return 1;
    }
 
    ll& ret = dp[n][m];
 
    if (ret != -1) {
        return ret;
    }
 
    ret = 0;
 
    for (int i = m / 2; i >= 1; i--) {
        ret += dfs(n - 1, i);
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int i = 1; i <= 10; i++) {
        for (int j = 1; j <= 2000; j++) {
            dp[i][j] = -1;
        }
    }
 
    for (int t = 0; t < T; t++) {
        cin >> n >> m;
 
        ll ans = 0;
 
        for (int i = m; i >= 1; i--) {
            ans += dfs(n, i);
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
반응형

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

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 스도쿠판을 입력받고, 백트래킹을 이용하여 모든 경우의 수를 체크합니다.

 

2. sero, garo, square 배열을 만들어 해당 줄과 칸에 숫자 존재 여부를 저장합니다.

 

3. 규칙에 맞게 스도쿠판이 채워지면 스도쿠판을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int arr[9][9];
int sero[9][10];
int garo[9][10];
int square[9][10];
bool flag = false;
 
void dfs(int num)
{
    if (flag) return;
    if (num == 81) {
        flag = true;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << arr[i][j] << ' ';
            }
            cout << '\n';
        }
    }
 
    int y = num / 9;
    int x = num % 9;
 
    if (arr[y][x] == 0) {
        for (int i = 1; i <= 9; i++) {
            if (sero[x][i] != 1 && garo[y][i] != 1 && square[(y / 3) * 3 + x / 3][i] != 1) {
                sero[x][i] = 1;
                garo[y][i] = 1;
                square[(y / 3) * 3 + x / 3][i] = 1;
                arr[y][x] = i;
                dfs(num + 1);
                sero[x][i] = 0;
                garo[y][i] = 0;
                square[(y / 3) * 3 + x / 3][i] = 0;
                arr[y][x] = 0;
            }
        }
    }
    else {
        dfs(num + 1);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> arr[i][j];
            if (arr[i][j] != 0) {
                sero[j][arr[i][j]] = 1;
                garo[i][arr[i][j]] = 1;
                square[(i / 3) * 3 + j / 3][arr[i][j]] = 1;
            }
        }
    }
 
    dfs(0);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
반응형

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

 

4343번: Arctic Network

The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열과 연결된 노드의 개수를 저장할 cnt를 선언합니다.

 

2. vect[ i ] = i로 초기화하고, 각 지점까지의 거리를  arr 배열에 저장합니다.

 

3. arr 배열을 거리를 기준으로 오름차순으로 정렬합니다.

 

4. Union-Find를 이용하여 각 지점들을 연결하고, 연결될 때마다 cnt++를 해주고, cnt == P - S일 때 거리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int u, v;
    double d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int T, S, P;
vector<node> arr;
pair<int, int> pos[501];
int vect[501];
int cnt;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int u, int v)
{
    int pu = Find(u);
    int pv = Find(v);
 
    vect[pv] = pu;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    cout << fixed;
    cout.precision(2);
 
    for (int t = 0; t < T; t++) {
        cin >> S >> P;
 
        arr.clear();
        cnt = 0;
 
        for (int i = 1; i <= P; i++) {
            int x, y;
            cin >> x >> y;
            pos[i] = { x,y };
            vect[i] = i;
        }
 
        for (int i = 1; i <= P - 1; i++) {
            for (int j = i + 1; j <= P; j++) {
                int x = pos[i].first - pos[j].first;
                int y = pos[i].second - pos[j].second;
                double d = sqrt(x * x + y * y);
                arr.push_back({ i,j,d });
            }
        }
 
        sort(arr.begin(), arr.end(), cmp);
 
        for (auto& next : arr) {
            const int u = next.u;
            const int v = next.v;
            const double d = next.d;
 
            if (Find(u) != Find(v)) {
                Union(u, v);
                cnt++;
            }
 
            if (cnt == P - S) {
                cout << d << '\n';
                break;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
반응형

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

 

2463번: 비용

첫 번째 줄에 정점의 수 N (1< ≤ N ≤ 100,000)과 간선의 수 M (1 ≤ M ≤ 100,000)이 빈칸을 사이에 두고 주어진다. 다음 M개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 x,y,w가 빈칸

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열과 연결된 노드의 개수를 저장할 cnt 배열을 선언합니다.

 

2. vect[ i ] = i, cnt[ i ] = 1로 초기화하고, 모든 간선의 길이를 더해 sum에 저장합니다.

 

3. 모든 간선을 저장할 arr 배열을 선언하고, 간선의 길이를 기준으로 내림차순으로 정렬합니다.

 

4. for문으로 arr 배열을 돌면서 Union-Find를 이용하여 노드들이 연결될 때마다 ans에 sum을 더해주고, sum에서 간선의 길이를 빼줍니다.

 

5. ans % 1,000,000,000을 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct edge {
    int u, v, c;
};
 
int N, M;
edge arr[100000];
int vect[100001];
int cnt[100001];
 
bool cmp(edge left, edge right)
{
    return left.c > right.c;
}
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = vect[a];
    int pb = vect[b];
 
    vect[pb] = pa;
    cnt[pa] += cnt[pb];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    ll sum = 0;
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        cnt[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        arr[i] = { u,v,c };
 
        sum += c;
    }
 
    sort(arr, arr + M, cmp);
 
    ll ans = 0;
 
    for (int i = 0; i < M; i++) {
        const int u = arr[i].u;
        const int v = arr[i].v;
        const int c = arr[i].c;
 
        if (Find(u) != Find(v)) {
            ans += sum * cnt[Find(u)] * cnt[Find(v)];
            Union(u, v);
        }
 
        sum -= c;
    }
 
    cout << ans % 1000000000;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
반응형

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

 

2479번: 경로 찾기

길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 코드를 입력받아 str 배열에 저장합니다.

 

2. 각각의 코드들을 서로 비교하면서 다른 자릿수가 1개만 존재하는 쌍들로 list 배열을 만들어 저장합니다.

 

3. bfs를 이용하여 A부터 B까지 경로가 존재하면 경로를 저장해 해당 경로를 출력하고, 그렇지 않으면 -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
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<queue>
#include<vector>
#include<string>
 
using namespace std;
 
int N, K;
vector<int> list[1001];
int visited[1001];
string str[1001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> K;
 
    for (int i = 1; i <= N; i++) {
        cin >> str[i];
    }
 
    for (int i = 1; i < N; i++) {
        for (int j = i + 1; j <= N; j++) {
            int cnt = 0;
            for (int k = 0; k < K; k++) {
                if (str[i][k] != str[j][k]) {
                    cnt++;
                }
                if (cnt > 1) break;
            }
            if (cnt == 1) {
                list[i].push_back(j);
                list[j].push_back(i);
            }
        }
    }
 
    queue<pair<int, vector<int>>>q;
 
    int A, B;
    cin >> A >> B;
 
    q.push({ A,{} });
    visited[A] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().first;
        vector<int> route = q.front().second;
        q.pop();
 
        route.push_back(cur);
 
        if (cur == B) {
            for (auto& next : route) {
                cout << next << ' ';
            }
            return 0;
        }
 
        for (auto& next : list[cur]) {
            if (visited[next] != 1) {
                visited[next] = 1;
                q.push({ next,route });
            }
        }
    }
 
    cout << -1;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
반응형

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

 

2591번: 숫자카드

1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다. 나중

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 차례로 적어 놓은 숫자를 저장하고, 점화식을 이용하여 문제를 풉니다.

 

2. 만약 str[ i ] 가 0이라면 ans[ i - 1 ] = 0, ans[ i ] = ans[ i - 2 ]의 식을 사용합니다.

 

3. 만약 str[ i - 1 ]과 str[ i ]의 숫자를 조합했을 때 34보다 작거나 같다면 ans[ i ] = ans[ i - 1 ] + ans [ i - 2 ]의 식을 사용하고, 그렇지 않다면 ans[ i ] = ans [ i - 1]의 식을 사용합니다.

 

4. ans[ str.size() - 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
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<string>
 
using namespace std;
 
int ans[40];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string str;
 
    cin >> str;
 
    ans[0] = 1;
    if (str[1] - '0' == 0) {
        ans[1] = 1;
        ans[0] = 0;
    }
    else {
        if ((str[0] - '0') * 10 + str[1] - '0' <= 34) {
            ans[1] = 2;
        }
        else {
            ans[1] = 1;
        }
    }
 
    for (int i = 2; i < str.size(); i++) {
        if (str[i] - '0' == 0) {
            ans[i] = ans[i - 2];
            ans[i - 1] = 0;
        }
        else {
            if ((str[i - 1] - '0') * 10 + str[i] - '0' <= 34) {
                ans[i] = ans[i - 2] + ans[i - 1];
            }
            else {
                ans[i] = ans[i - 1];
            }
        }
    }
 
    cout << ans[str.size() - 1];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
[ 백준 ] 3067번 - Coins (C++)  (0) 2023.08.18
반응형

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

 

2116번: 주사위 쌓기

첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 주사위를 입력받고, 첫 주사위의 바닥이 A일 때부터 F일 때까지 for문을 통해 돌면서 모든 경우의 수를 구합니다.

 

2. 주사위의 바닥이 정해지면 윗면이 정해지고, 두 면을 제외한 나머지 수 중 가장 큰 수를 Max에 저장하고, 쌓여 있는 모든 주사위의 옆면 중 Max 값을 ret에 더해줍니다.

 

3. ret 값중 가장 큰 값을 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
#include<iostream>
 
using namespace std;
 
int N;
int arr[10000][6];
int ans;
 
int getSum(int n)
{
    int temp = arr[0][n];
    int idx = n;
    int ret = 0;
    int Max = 0;
 
    for (int i = 0; i < N; i++) {
        Max = 0;
 
        for (int j = 0; j < 6; j++) {
            if (arr[i][j] == temp) {
                idx = j;
                break;
            }
        }
 
        if (idx == 0 || idx == 5) {
            for (int j = 0; j < 6; j++) {
                if (j != 0 && j != 5) {
                    Max = max(Max, arr[i][j]);
                }
            }
 
            if (idx == 0) {
                temp = arr[i][5];
            }
            else {
                temp = arr[i][0];
            }
        }
        else if (idx == 1 || idx == 3) {
            for (int j = 0; j < 6; j++) {
                if (j != 1 && j != 3) {
                    Max = max(Max, arr[i][j]);
                }
            }
 
            if (idx == 1) {
                temp = arr[i][3];
            }
            else {
                temp = arr[i][1];
            }
        }
        else {
            for (int j = 0; j < 6; j++) {
                if (j != 2 && j != 4) {
                    Max = max(Max, arr[i][j]);
                }
            }
 
            if (idx == 2) {
                temp = arr[i][4];
            }
            else {
                temp = arr[i][2];
            }
        }
 
        ret += Max;
    }
 
    return ret;
}
 
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 < 6; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < 6; i++) {
        ans = max(ans, getSum(i));
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
[ 백준 ] 3067번 - Coins (C++)  (0) 2023.08.18
[ 백준 ] 16965번 - 구간과 쿼리 (C++)  (0) 2023.08.17
반응형

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

 

10216번: Count Circle Groups

백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 진영의 위치와 R을 입력받아 arr에 저장하고, visited 배열을 만들어 각 진영의 방문 여부를 체크해 줍니다.

 

2. for문을 통해 모든 진영을 돌면서 visited[ i ] 가 0이라면 ans++를 해주고 bfs를 돌며 이어진 진영의 visited를 1로 갱신해 줍니다.

 

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
#include<iostream>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int x, y, R;
};
 
int T, N;
node arr[3000];
int visited[3000];
 
void bfs(int num)
{
    queue<int> q;
 
    q.push(num);
 
    while (!q.empty()) {
        const int x = arr[q.front()].x;
        const int y = arr[q.front()].y;
        const int R = arr[q.front()].R;
        q.pop();
 
        for (int i = 0; i < N; i++) {
            if (visited[i] == 0) {
                const int xx = arr[i].x;
                const int yy = arr[i].y;
                const int RR = arr[i].R;
 
                if (sqrt(pow(x - xx, 2) + pow(y - yy, 2)) <= R + RR) {
                    visited[i] = 1;
                    q.push(i);
                }
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        cin >> N;
 
        for (int i = 0; i < N; i++) {
            int x, y, R;
            cin >> x >> y >> R;
            arr[i] = { x,y,R };
        }
 
        int ans = 0;
        fill(visited, visited + N, 0);
 
        for (int i = 0; i < N; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                bfs(i);
                ans++;
            }
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 3067번 - Coins (C++)  (0) 2023.08.18
[ 백준 ] 16965번 - 구간과 쿼리 (C++)  (0) 2023.08.17
[ 백준 ] 20007번 - 떡 돌리기 (C++)  (0) 2023.08.16
반응형

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

 

3067번: Coins

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/20

 

[ 백준 ] 12865번 - 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1

rudalsd.tistory.com

 

1. 점화식 dp[ i ][ j ] = dp[ i ][ j - coin[ i ] ] + dp[ i - 1 ][ j ] 을 통해 방법의 수를 구합니다.

 

2. dp[ N ][ M ] 을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int T;
int coin[21];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        int N, M;
        cin >> N;
        int dp[21][10001] = { 0 };
        for (int i = 1; i <= N; i++) {
            cin >> coin[i];
            dp[i][0] = 1;
        }
 
        cin >> M;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (j < coin[i]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i][j - coin[i]] + dp[i - 1][j];
            }
        }
 
        cout << dp[N][M] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
[ 백준 ] 16965번 - 구간과 쿼리 (C++)  (0) 2023.08.17
[ 백준 ] 20007번 - 떡 돌리기 (C++)  (0) 2023.08.16
[ 백준 ] 2224번 - 명제 증명 (C++)  (0) 2023.08.15

+ Recent posts

티스토리툴바