반응형

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

 

16936번: 나3곱2

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

2. 재귀함수를 이용하여 수열을 채워 나가는데, 이전 값에 2를 곱한 값이나 3을 나눈 값이 현재 수열의 값일 때만 수열에 넣어줍니다.

 

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
ll arr[100];
ll ans[100];
int visited[100];
bool flag = false;
 
void dfs(int level)
{
    if (flag) return;
 
    if (level == N) {
        for (int i = 0; i < N; i++) {
            cout << ans[i] << ' ';
        }
 
        flag = true;
    }
 
    for (int i = 0; i < N; i++) {
        if (visited[i] == 0 && (ans[level-1] * 2 == arr[i] || (ans[level-1] % 3 == 0 && ans[level - 1] / 3 == arr[i]))) {
            visited[i] = 1;
            ans[level] = arr[i];
            dfs(level + 1);
            visited[i] = 0;
            ans[level] = 0;
        }
    }
}
 
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];
    }
 
    for (int i = 0; i < N; i++) {
        visited[i] = 1;
        ans[0] = arr[i];
        dfs(1);
        ans[0] = 0;
        visited[i] = 0;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
반응형

 

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

 

20168번: 골목 대장 호석 - 기능성

첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 교차차로를 입력받아 vector list에 저장하고, visited[ cost ][ node ]를 만들어 지나온 길 중 가장 큰 비용이 cost이고, 해당 node에 도착했을 때 총비용을 저장합니다.

 

2. bfs를 통해 A부터 노드들을 돌면서 B에 도착했을 때 cost의 최솟값을 ans에 저장합니다.

 

3. ans의 값이 987654321이라면 -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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
struct node {
    int cur;
    int cost;
    int shame;
};
 
int N, M, A, B, C;
int visited[1001][11];
vector<pair<int,int>> list[11];
int ans = 987654321;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> A >> B >> C;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 1000; j++) {
            visited[j][i] = 987654321;
        }
    }
    
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
 
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    queue<node> q;
 
    q.push({ A,0,0 });
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int cost = q.front().cost;
        const int shame = q.front().shame;
        q.pop();
 
        if (cur == B) {
            ans = min(ans, shame);
            continue;
        }
 
        if (visited[shame][cur] < cost) continue;
        visited[shame][cur] = cost;
 
        for (auto& next : list[cur]) {
            int Max = max(shame, next.second);
            if (visited[Max][next.first] > cost + next.second && cost + next.second <= C) {
                visited[Max][next.first] = cost + next.second;
                q.push({ next.first,cost + next.second, Max });
            }
        }
    }
 
    if (ans == 987654321) cout << -1;
    else cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2224번 - 명제 증명 (C++)  (0) 2023.08.15
[ 백준 ] 20182번 - 골목 대장 호석 - 효율성 1 (C++)  (0) 2023.08.14
[ 백준 ] 16472번 - 고냥이 (C++)  (0) 2023.08.12
[ 백준 ] 9024번 - 두 수의 합 (C++)  (0) 2023.08.11
[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
반응형

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

 

7490번: 0 만들기

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 백트래킹을 이용해 실시간으로 계산값들을 저장하고, 각 인덱스에 저장되어 있는 부호가 무엇인지 저장합니다.

 

2. 만약 계산값이 0이라면 vector<stirng> ans에 숫자와 부호를 push합니다.

 

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>
#include<vector>
#include<string>
#include<algorithm>
 
using namespace std;
 
int N;
int ret = 0;
char box[10];
vector<string> ans;
 
void dfs(int level, int num, int idx)
{
    if (level == N + 1) {
        if (num != 0) {
            if (box[idx] == '-') {
                ret -= num;
            }
            else {
                ret += num;
            }
        }
        if (ret == 0) {
            string temp;
            for (int i = 1; i <= N; i++) {
                temp += '0' + i;
                temp += box[i];
            }
            ans.push_back(temp);
        }
        if (num != 0) {
            if (box[idx] == '-') {
                ret += num;
            }
            else {
                ret -= num;
            }
        }
        return;
    }
 
    num = num * 10 + level;
 
    if (N != level) {
        if (box[idx] == '-') {
            ret -= num;
            box[level] = '+';
            dfs(level + 1, 0, level);
            box[level] = '-';
            dfs(level + 1, 0, level);
            ret += num;
            box[level] = 0;
        }
        else {
            ret += num;
            box[level] = '+';
            dfs(level + 1, 0, level);
            box[level] = '-';
            dfs(level + 1, 0, level);
            ret -= num;
            box[level] = 0;
        }
    }
 
    box[level] = ' ';
    dfs(level + 1, num, idx);
    box[level] = 0;
 
    return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        ans.clear();
        cin >> N;
 
        dfs(1,0,0);
 
        sort(ans.begin(), ans.end());
 
        for (auto& next : ans) {
            cout << next << '\n';
        }
 
        cout << '\n';
    }
}
cs

 

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14497번 - 주난의 난(難) (C++)  (0) 2023.06.16
[ 백준 ] 10464번 - XOR (C++)  (0) 2023.06.15
[ 백준 ] 20437번 - 문자열 게임 2 (C++)  (0) 2023.06.13
[ 백준 ] 12919번 - A와 B 2 (C++)  (0) 2023.06.12
[ 백준 ] 14463번 - 소가 길을 건너간 이유 9 (C++)  (0) 2023.06.11

+ Recent posts

티스토리툴바