반응형

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

 

15918번: 랭퍼든 수열쟁이야!!

세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. n, x, y를 입력받고, arr[ x ] = arr [ y ] = y - x - 1로 초기화합니다.

 

2. 백트래킹을 이용하여 수열의 자리를 채우고, 수열이 완성되면 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
#include<iostream>
 
using namespace std;
 
int n, x, y;
int arr[25];
int visited[13];
int ans;
 
void dfs(int level)
{
    if (level == 2 * n + 1) {
        ans++;
        return;
    }
    if (arr[level]) dfs(level + 1);
 
    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0 && level + i + 1 <= 2 * n && arr[level] == 0 && arr[level + i + 1] == 0) {
            visited[i] = 1;
            arr[level] = i;
            arr[level + i + 1] = i;
            dfs(level + 1);
            visited[i] = 0;
            arr[level] = 0;
            arr[level + i + 1] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> x >> y;
 
    arr[x] = arr[y] = y - x - 1;
    visited[y - x - 1] = 1;
 
    dfs(1);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
반응형

 

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

 

3967번: 매직 스타

매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 매직 스타를 입력받고, 채워지지 않은 위치를 pos에 저장합니다.

 

2. 재귀함수를 이용하여 각 자리에 알파벳을 채워주고, 각 줄의 합이 282보다 크다면 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
 
string str[5];
char arr[12];
int visited[12];
vector<int> pos;
bool flag = false;
 
void dfs(int level)
{
    if (flag) return;
    if (arr[1] + arr[2] + arr[3] + arr[4] > 282) return;
    if (arr[0] + arr[2] + arr[5] + arr[7] > 282) return;
    if (arr[0] + arr[3] + arr[6] + arr[10] > 282) return;
    if (arr[7] + arr[8] + arr[9] + arr[10] > 282) return;
    if (arr[1] + arr[5] + arr[8] + arr[11] > 282) return;
    if (arr[4] + arr[6] + arr[9] + arr[11] > 282) return;
 
    if (level == pos.size()) {
        int cnt = 0;
        flag = true;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                if (str[i][j] != '.') {
                    cout << arr[cnt++];
                }
                else {
                    cout << str[i][j];
                }
            }
            cout << '\n';
        }
        return;
    }
 
    for (int i = 0; i < 12; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            arr[pos[level]] = i + 'A';
            dfs(level + 1);
            visited[i] = 0;
            arr[pos[level]] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 5; i++) {
        cin >> str[i];
    }
 
    int cnt = 0;
 
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 9; j++) {
            if (str[i][j] != '.') {
                if (str[i][j] == 'x') {
                    pos.push_back(cnt++);
                }
                else {
                    visited[str[i][j] - 'A'] = 1;
                    arr[cnt++] = str[i][j];
                }
            }
        }
    }
 
    dfs(0);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
반응형

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/12919

 

12919번: A와 B 2

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. unordered_map을 활용하여 문자열의 방문 여부를 저장합니다.

 

2. T문자열부터 시작하여 맨 뒤 문자가 'A'일 때와 맨 앞 문자가 'B'일 때 두 상황에서 각각 처리한 뒤 queue에 넣어주면서 S문자열과 같아지면 1을 출력하고 프로그램을 종료시킵니다.

 

3.  S문자열을 만들 수 없다면 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<string>
#include<queue>
#include<unordered_map>
 
using namespace std;
 
string S, T;
unordered_map<string, int> visited;
 
string change(string S)
{
    string temp;
 
    for (int i = S.size()-1; i >= 0; i--) {
        temp += S[i];
    }
 
    return temp;
}
 
int main()
{
    cin >> S >> T;
 
    queue<string> q;
 
    q.push(T);
    visited[T] = 1;
 
    while (!q.empty()) {
        string A = q.front();
        q.pop();
 
        if (A == S) {
            printf("1");
            return 0;
        }
        if (A.size() == S.size()) continue;
 
        string temp = A;
        if (temp[temp.size() - 1] == 'A') {
            temp.erase(temp.end() - 1);
            if (visited[temp] != 1) {
                visited[temp] = 1;
                q.push(temp);
            }
        }
 
        temp = A;
 
        if (temp[0] == 'B') {
            temp = change(temp);
            temp.erase(temp.end() - 1);
            if (visited[temp] != 1) {
                visited[temp] = 1;
                q.push(temp);
            }
        }
    }
 
    printf("0");
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 7490번 - 0 만들기 (C++)  (0) 2023.06.14
[ 백준 ] 20437번 - 문자열 게임 2 (C++)  (0) 2023.06.13
[ 백준 ] 14463번 - 소가 길을 건너간 이유 9 (C++)  (0) 2023.06.11
[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
반응형

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

 

11376번: 열혈강호 2

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고,

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/384

 

[ 알고리즘 ] 이분 매칭(Bipartite Matching)

1. 이분 매칭(Bipartite Matching)이란? 정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 이분 그래프(Bipartite Graph)라고 말합니다.

rudalsd.tistory.com

 

1. 한 명이 총 2개의 일을 할 수 있으므로 N * 2의 범위까지 사람을 늘리고, i * 2 와 i * 2 - 1 을 한 사람으로 생각하고 문제를 풉니다.

 

2. 이분 매칭을 이용하여 매칭이 될 때마다 ans에 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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
vector<int> list[2001];
int visited[2001];
int work[1001];
int cnt;
 
bool dfs(int cur)
{
    if (visited[cur] == cnt) return false;
    visited[cur] = cnt;
 
    for (int& next : list[cur]) {
        if (!work[next] || dfs(work[next])) {
            work[next] = cur;
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        int n;
        scanf("%d", &n);
 
        for (int j = 0; j < n; j++) {
            int m;
            scanf("%d", &m);
 
            list[i * 2].push_back(m);
            list[i * 2 - 1].push_back(m);
        }
    }
 
    int ans = 0;
 
    for (int i = 1; i <= N * 2; i++) {
        cnt++;
        if(dfs(i)) ans++;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
[ 백준 ] 18116번 - 로봇 조립 (C++)  (0) 2023.05.27
[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
반응형

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

 

1780번: 종이의 개수

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수

www.acmicpc.net

 

 

[ 문제풀이 ]

 

분할 정복을 통해서 문제를 풀었습니다.

 

1. 원하는 부분의 숫자가 모두 같은 지 판단합니다.

 

2. 숫자가 다르다면 다시 9구역으로 나누어 1번을 반복합니다.

 

3. 숫자가 같다면 ans 배열에 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
#include<iostream>
 
using namespace std;
 
int N;
int arr[2200][2200];
int ans[3];
 
void conquer(int y1, int y2, int x1, int x2)
{
    int flag = 0;
    int cur = arr[y1][x1];
    for (int i = y1; i < y2; i++) {        //모두 같은 수인지
        for (int j = x1; j < x2; j++) {
            if (cur != arr[i][j]) {
                flag = 1;
                break;
            }
 
        }
    }
 
    int y = (y2 - y1) / 3;
    int x = (x2 - x1) / 3;
 
    if (flag == 0) {        //같은 수라면
        ans[cur + 1]++;
    }
    else {        //다른 수가 있다면
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                conquer(y1 + y * i, y1 + y * (i + 1), x1 + x * j, x1 + x * (j + 1));
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    conquer(0, N, 0, N);
 
    for (int i = 0; i < 3; i++) {
        printf("%d\n", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11286번 - 절댓값 힙 (C++)  (0) 2022.08.23
[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
반응형

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

 

5639번: 이진 검색 트리

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

입력받은 수의 부모 노드를 기준으로 왼쪽에 있는 노드와 오른쪽에 있는 노드를 구분하여 왼쪽 노드부터 출력해주면 됩니다.

 

현재 노드에서 값이 커지는 부분이 오른쪽 노드이므로 for문을 돌려서 현재 노드 +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
#include<iostream>
 
using namespace std;
 
int arr[10000];
int i;
 
void dfs(int node, int size)
{
    if (node >= size) return;
 
    for (i = node + 1; i < size; i++) {
        if (arr[node] < arr[i]) break;
    }
 
    dfs(node + 1, i);    //왼쪽
    dfs(i, size);        //오른쪽
    printf("%d\n", arr[node]);
 
    return;
}
 
int main()
{
    int idx = 0;
 
    while (scanf("%d", &arr[idx]) != EOF)
    {
        idx++;
    }
 
    dfs(0, idx);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11505번 - 구간 곱 구하기 (C++)  (0) 2022.07.09
[ 백준 ] 2096번 - 내려가기 (C++)  (0) 2022.07.08
[ 백준 ] 14502번 - 연구소 (C++)  (0) 2022.07.06
[ 백준 ] 2357번 - 최솟값과 최댓값 (C++)  (0) 2022.07.05
[ 백준 ] 2042번 - 구간 합 구하기 (C++)  (0) 2022.07.04

+ Recent posts

티스토리툴바