반응형

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

 

2661번: 좋은수열

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N을 입력받고, 백트래킹을 이용해 수열을 만들어줍니다.

 

2. check 함수를 만들어 해당 수열이 좋은 수열인지 판별한 후 좋은 수열이 아니라면 return 해줍니다. 

 

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
#include<iostream>
 
using namespace std;
 
int N;
int arr[80];
bool ans = false;
 
bool check(int N)
{
    bool same = true;
 
    for (int k = 1; k <= N; k++) {
        for (int i = 0; i <= N - k - k; i++) {
            same = true;
            for (int j = 0; j < k; j++) {
                if (arr[i + j] != arr[i + k + j]) {
                    same = false;
                    continue;
                }
            }
            if (same) return false;
        }
    }
 
    return true;
}
 
void dfs(int level)
{
    if (!check(level)) return;
    if (ans) return;
    if (level == N) {
        for (int i = 0; i < N; i++) {
            cout << arr[i];
        }
        ans = true;
        return;
    }
 
    for (int i = 1; i <= 3; i++) {
        if (arr[level - 1] != i) {
            arr[level] = i;
            dfs(level + 1);
            arr[level] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    if (N == 1) cout << 1;
    else dfs(0);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17299번 - 오등큰수 (C++)  (1) 2023.10.06
[ 백준 ] 2186번 - 문자판 (C++)  (1) 2023.10.05
[ 백준 ] 1461번 - 도서관 (C++)  (0) 2023.10.03
[ 백준 ] 1354번 - 무한 수열 2 (C++)  (0) 2023.10.02
[ 백준 ] 2174번 - 로봇 시뮬레이션 (C++)  (0) 2023.10.01
반응형

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

 

20924번: 트리의 기둥과 가지

첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받고, list 배열에 저장합니다.

 

2. dfs를 이용하여 루트부터 탐색하면서 현재 노드까지의 길이를 저장하고, 그중 가장 긴 길이를 all에 저장합니다.

 

3. 자식 노드가 2개 이상인 노드의 길이 중 가장 짧은 길이를 gidung에 저장합니다.

 

4. gidung 과 all - gidung을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, R;
int a, b, d;
vector<pair<int, int>> list[200001];
int visited[200001];
int all;
int gidung = 987654321;
 
void dfs(int node, int dist)
{
    int cnt = 0;
    all = max(all, dist);
    for (auto& next : list[node]) {
        if (visited[next.first] == 0) {
            cnt++;
            visited[next.first] = 1;
            dfs(next.first, dist + next.second);
            visited[next.first] = 0;
        }
    }
 
    if (cnt >= 2) {
        gidung = min(gidung, dist);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> R;
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, d;
        cin >> a >> b >> d;
 
        list[a].push_back({ b,d });
        list[b].push_back({ a,d });
    }
 
    visited[R] = 1;
    dfs(R, 0);
 
    if (gidung == 987654321) {
        gidung = all;
    }
 
    cout << gidung << ' ' << all - gidung;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1351번 - 무한 수열 (C++)  (0) 2023.09.28
[ 백준 ] 14925번 - 목장 건설하기 (C++)  (0) 2023.09.27
[ 백준 ] 10835번 - 카드게임 (C++)  (0) 2023.09.25
[ 백준 ] 3197번 - 백조의 호수 (C++)  (0) 2023.09.24
[ 백준 ] 2015번 - 수들의 합 4 (C++)  (0) 2023.09.23
반응형

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

 

13565번: 침투

첫째 줄에는 격자의 크기를 나타내는  M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 격자를 입력받고, 격자의 y 좌표가 0인 좌표의 arr 값이 '0'이라면 queue에 넣고, visited 배열을 만들어 방문 여부를 저장합니다.

 

2. bfs를 이용하여 arr의 값이 '0'인 좌표로만 이동하면서 y 좌표의 값이 M이상인 경우가 있다면 YES를, 그렇지 않다면 NO를 출력합니다.

 

[ 소스코드 ]

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<queue>
 
using namespace std;
 
int M, N;
char arr[1000][1001];
int visited[1000][1000];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> M >> N;
 
    for (int i = 0; i < M; i++) {
        cin >> arr[i];
    }
 
    queue<pair<int, int>> q;
 
    for (int i = 0; i < N; i++) {
        if (arr[0][i] == '0') {
            q.push({ 0,i });
            visited[0][i] = 1;
        }
    }
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < M && xx >= 0 && xx < N) {
                if (visited[yy][xx] == 0 && arr[yy][xx] == '0') {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
            else if (yy == M) {
                cout << "YES";
                return 0;
            }
        }
    }
 
    cout << "NO";
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 3197번 - 백조의 호수 (C++)  (0) 2023.09.24
[ 백준 ] 2015번 - 수들의 합 4 (C++)  (0) 2023.09.23
[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21
[ 백준 ] 12016번 - 라운드 로빈 스케줄러 (C++)  (0) 2023.09.20
[ 백준 ] 17609번 - 회문 (C++)  (0) 2023.09.19
반응형

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

 

3184번: 양

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, v와 o의 개수를 세어 ans에 저장해 줍니다.

 

2. 방문하지 않은 좌표들을 방문하면서, bfs를 돌려주고, 각 영역의 양과 늑대의 수를 세어주고, 늑대가 양보다 많다면 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
#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
int R, C;
string arr[250];
int visited[250][250];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
pair<int, int> ans;
 
void bfs(int y, int x)
{
    int v = 0, o = 0;
 
    queue<pair<int, int>> q;
 
    q.push({ y,x });
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        if (arr[y][x] == 'v') v++;
        else if (arr[y][x] == 'o') o++;
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < R && xx >= 0 && xx < C) {
                if (visited[yy][xx] == 0 && arr[yy][xx] != '#') {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    if (v >= o) {
        ans.first -= o;
    }
    else {
        ans.second -= v;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] == 'v') {
                ans.second++;
            }
            else if(arr[i][j] == 'o') {
                ans.first++;
            }
        }
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (visited[i][j] == 0 && arr[i][j] != '#') {
                visited[i][j] = 1;
                bfs(i, j);
            }
        }
    }
 
    cout << ans.first << ' ' << ans.second;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
반응형

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

 

7299번: Food Cubes

The spacemen in the space shuttle are waiting for the next escape window to return to the mother land Earth, where they are expected to fall somewhere in the deep blue waters of the Persian Gulf. Bored of waiting with nothing to do, they decide to play a g

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 좌표를 입력받아 해당 좌표의 값을 arr 배열에 1로 저장하고, visited 배열을 선언하여 방문여부를 체크합니다.

 

2. 모든 좌표를 돌면서 방문하지 않은 좌표에서 bfs를 이용하여 주변에 음식이 있는지 체크하고, 좌표 범위를 벗어나면 ret를 false로 갱신합니다. 

 

3. true일 때 ans++를 해주고, 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
#include<iostream>
#include<queue>
 
using namespace std;
 
struct node {
    int x, y, z;
};
 
int T, M;
int arr[101][101][101];
int visited[101][101][101];
int dx[] = { -1,1,0,0,0,0 };
int dy[] = { 0,0,-1,1,0,0 };
int dz[] = { 0,0,0,0,-1,1 };
 
bool bfs(int x, int y, int z)
{
    bool ret = true;
 
    queue<node> q;
    q.push({ x,y,z });
 
    while (!q.empty()) {
        const int x = q.front().x;
        const int y = q.front().y;
        const int z = q.front().z;
        q.pop();
 
        for (int i = 0; i < 6; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            int zz = z + dz[i];
 
            if (xx >= 1 && xx <= 100 && yy >= 1 && yy <= 100 && zz >= 1 && zz <= 100) {
                if (visited[xx][yy][zz] == 0 && arr[xx][yy][zz] == 0) {
                    visited[xx][yy][zz] = 1;
                    q.push({ xx,yy,zz });
                }
            }
            else {
                ret = false;
            }
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> M;
 
        for (int i = 1; i <= 100; i++) {
            for (int j = 1; j <= 100; j++) {
                for (int k = 1; k <= 100; k++) {
                    visited[i][j][k] = 0;
                    arr[i][j][k] = 0;
                }
            }
        }
 
        for (int i = 0; i < M; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            arr[x][y][z] = 1;
        }
 
        int ans = 0;
 
        for (int i = 1; i <= 100; i++) {
            for (int j = 1; j <= 100; j++) {
                for (int k = 1; k <= 100; k++) {
                    if (arr[i][j][k] == 0 && visited[i][j][k] == 0) {
                        visited[i][j][k] = 1;
                        if (bfs(i, j, k)) ans++;
                    }
                }
            }
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
반응형

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

 

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 문자의 자릿수 값을 저장할 box 배열을 선언합니다.

 

2. 각 단어가 입력될 때마다 각 자릿수의 문자에 10의 n승을 곱해 더해줍니다.

 

3. box 배열을 내림차순으로 정렬하고, box[ 0 ] ~ box[ 9 ] 까지의 값에 9 ~ 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
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
 
using namespace std;
 
int N;
int box[26];
int ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
 
        for (int j = 0; j < str.size(); j++) {
            box[str[j] - 'A'] += pow(10, str.size() - j - 1);
        }
    }
 
    sort(box, box + 26, greater<>());
 
    int seq = 0;
 
    for (int i = 9; i >= 0; i--) {
        ans += box[seq] * i;
        seq++;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
반응형

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

 

6067번: Guarding the Farm

There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받아 arr 배열에 저장하고, visited 배열을 선언하여 방문여부를 체크합니다.

 

2. 모든 좌표를 돌면서 방문하지 않은 좌표에서 bfs를 이용하여 주변에 더 높은 지형이 있는지 체크하고 더 높은 지형이 없다면 true를 아니라면 false를 return 합니다.

 

3. true일 때 ans++를 해주고, 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>
 
using namespace std;
 
int N, M;
int arr[700][700];
int visited[700][700];
int dy[] = { -1,-1,0,1,1,1,0,-1 };
int dx[] = { 0,1,1,1,0,-1,-1,-1 };
 
bool bfs(int y, int x)
{
    queue<pair<int, int>> q;
 
    q.push({ y,x });
 
    bool ret = true;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (visited[yy][xx] != 1 && arr[yy][xx] == arr[y][x]) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
                else if (arr[yy][xx] > arr[y][x]) {
                    ret = false;
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] != 1) {
                visited[i][j] = 1;
                if (bfs(i, j)) {
                    ans++;
                }
            }
        }
    }
 
    cout << ans;
}
cs

 

반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
반응형

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

 

16929번: Two Dots

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 게임판을 arr 배열에 입력받고, 최종 방문 여부를 저장할 visited2 배열과, dfs를 돌면서 방문을 기록할 visited 배열을 만듭니다.

 

2. 모든 좌표를 돌면서 visited2 배열의 값이 0일 때 dfs를 돌면서 방문한 곳에 한번 더 방문할 때 점의 개수가 4개 이상일 경우 ans의 값을 true로 바꿔줍니다.

 

3. ans가 true이면 Yes를 출력하고, 그렇지 않다면 No를 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int N, M;
char arr[51][51];
int visited[51][51];
int visited2[51][51];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
bool ans = false;
 
void dfs(int y, int x, int cnt)
{
    if (ans == true) return;
    visited2[y][x] = 1;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
 
        if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
            if (arr[yy][xx] == arr[y][x]) {
                if (visited[yy][xx] != 0) {
                    if (cnt - visited[yy][xx] + 1 >= 4) {
                        ans = true;
                        return;
                    }
                }
                else {
                    visited[yy][xx] = cnt + 1;
                    dfs(yy, xx, cnt + 1);
                    visited[yy][xx] = 0;
                }
            }
        }
    }
}
 
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 = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited2[i][j] == 0) {
                visited[i][j] = 1;
                dfs(i, j, 1);
                visited[i][j] = 0;
            }
        }
    }
 
    if (ans) cout << "Yes";
    else cout << "No";
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 16934번 - 게임 닉네임 (C++)  (0) 2023.07.25
[ 백준 ] 7432번 - 디스크 트리 (C++)  (0) 2023.07.24
[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20
반응형

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

 

1038번: 감소하는 수

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 감소하는 수의 최댓값은 9876543210이므로 감소하는 수의 자릿수의 최댓값은 10입니다.

 

2. 최대 자릿수를 1부터 10까지 for문을 돌면서 숫자들을 탐색하고, 감소하는 수가 나올 때마다 cnt++를 해주고, cnt == N이 될 때 해당 수를 출력해 줍니다.

 

3. 감소하는 수의 최대 개수는 1022개 이므로 N이 1023 이상이라면 -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
#include<iostream>
 
using namespace std;
 
int N;
int bucket[10];
int cnt = -1;
 
void dfs(int level, int limit)
{
    if (cnt >= N) return;
    if (level == 0) {
        cnt++;
        if (cnt == N) {
            for (int i = limit - 1; i >= 0; i--) {
                cout << bucket[i];
            }
        }
        return;
    }
 
    for (int i = level - 1; i < 10; i++) {
        if (level != limit) {
            if (bucket[level] > i) {
                bucket[level - 1] = i;
                dfs(level - 1, limit);
                bucket[level - 1] = 0;
            }
            else {
                return;
            }
        }
        else {
            bucket[level - 1] = i;
            dfs(level - 1, limit);
            bucket[level - 1] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    if (N > 1022) cout << -1;
 
    for (int i = 1; i <= 10; i++) {
        dfs(i, i);
        if (cnt >= N) break;
    }
 
    int de = -1;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 6198번 - 옥상 정원 꾸미기 (C++)  (0) 2023.07.07
[ 백준 ] 1456번 - 거의 소수 (C++)  (0) 2023.07.06
[ 백준 ] 11402번 - 이항 계수 4 (C++)  (0) 2023.07.04
[ 백준 ] 11401번 - 이항 계수 3 (C++)  (0) 2023.07.02
[ 백준 ] 17025번 - Icy Perimeter (C++)  (0) 2023.07.01
반응형

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

 

17025번: Icy Perimeter

Please output one line containing two space-separated integers, the first being the area of the largest blob, and the second being its perimeter. If multiple blobs are tied for largest area, print the information for whichever of these has the smallest per

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 각 방문 여부를 저장합니다.

 

2. 모든 좌표를 돌면서 해당 좌표가 #이고 방문하지 않았다면 bfs를 통해 블롭의 개수와 둘레 길이를 저장합니다.

 

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<queue>
 
using namespace std;
 
int N;
char arr[1001][1001];
int visited[1001][1001];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
pair<int,int> bfs(int y, int x)
{
    int ret = 1;
    int cnt = 0;
 
    queue<pair<int,int>> q;
 
    q.push({ y,x });
 
    visited[y][x] = 1;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (visited[yy][xx] != 1 && arr[yy][xx] == '#') {
                    ret++;
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
                else if(arr[yy][xx] == '.'){
                    cnt++;
                }
            }
            else {
                cnt++;
            }
        }
 
    }
 
    return make_pair(ret,cnt);
}
 
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];
    }
 
    int ans = 0;
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j] == 0 && arr[i][j] == '#') {
                pair<int, int> temp = bfs(i, j);
 
                if (ans < temp.first) {
                    ans = temp.first;
                    cnt = temp.second;
                }
                if (ans == temp.first) {
                    cnt = min(cnt, temp.second);
                }
            }
        }
    }
 
    cout << ans << ' ' << cnt;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11402번 - 이항 계수 4 (C++)  (0) 2023.07.04
[ 백준 ] 11401번 - 이항 계수 3 (C++)  (0) 2023.07.02
[ 백준 ] 8981번 - 입력숫자 (C++)  (0) 2023.06.30
[ 백준 ] 1863번 - 스카이라인 쉬운거 (C++)  (0) 2023.06.29
[ 백준 ] 12869번 - 뮤탈리스크 (C++)  (0) 2023.06.28

+ Recent posts

티스토리툴바