반응형

www.acmicpc.net/problem/10819

 

10819번: 차이를 최대로

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

www.acmicpc.net

1. 순열 순서 변경

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
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
int n, ans;
int arr[9];
using namespace std;
int calc() {
    int ret = 0;
    for (int i = 0;i < n - 1;i++)
        ret += abs(arr[i] - arr[i + 1]);
    return ret;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, n)
        cin >> arr[i];
    sort(arr, arr + n);
    ans = calc();
    while (next_permutation(arr, arr + n)) 
        ans = max(ans, calc());
    
    cout << ans;
}
cs
반응형

'백준 > 백트래킹' 카테고리의 다른 글

백준 18290  (0) 2021.02.15
백준 10971  (0) 2021.02.03
백준 1987  (0) 2021.02.03
백준 1759  (0) 2021.02.03
백준 1182  (0) 2021.01.30
반응형

www.acmicpc.net/problem/1987

 

1987번: 알파벳

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으

www.acmicpc.net

인접한 칸 탐색하면서 현재 몇 단계인지 체크, 최댓값과 비교. !visited일 때만 탐색

 

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
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int r, c;
char arr[21][21];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
bool visited[26];
int ans = 0;
void dfs(int x, int y, int step) {
    ans = ans > step ? ans : step;
    // 탐색
    rep(i, 4) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
            char next_char = arr[nx][ny];
            if (!visited[next_char - 'A']) {
                visited[next_char - 'A'] = true;
                dfs(nx, ny, step + 1);
                visited[next_char - 'A'] = false;
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> c;
    rep(i, r) {
        rep(j, c)
            cin >> arr[i][j];
    }
    visited[arr[0][0] - 'A'] = true;
    dfs(0, 0, 1);
    cout << ans;
}
cs
반응형

'백준 > 백트래킹' 카테고리의 다른 글

백준 10971  (0) 2021.02.03
백준 10819  (0) 2021.02.03
백준 1759  (0) 2021.02.03
백준 1182  (0) 2021.01.30
백준 6603  (0) 2021.01.30
반응형

www.acmicpc.net/problem/1759

 

1759번: 암호 만들기

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

www.acmicpc.net

1. n개 중 r개 뽑기

1
2
3
4
5
6
7
8
9
10
void dfs(int idx, int step) {
    if (step == l) {
        // 종료 조건
        return;
    }
    for (int i = idx; i < c; i++) {
        ans[step] = arr[i];
        dfs(i + 1, step + 1);
    }
}
 cs

2. 모음 최소 1개, 자음 최소 2개

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (step == l) {
    int cnt1 = 0, cnt2 = 0;
    rep(i, l) {
        if (ans[i] == 'a' || ans[i] == 'e' || ans[i] == 'i' || ans[i] == 'o' || ans[i] == 'u')
            cnt1++;
        else
            cnt2++;
        // 조건 만족하면 바로 출력
        if (cnt1 >= 1 && cnt2 >= 2) {
            rep(i, l)
                cout << ans[i];
            cout << '\n';
            return;
        }
    }
    return;
}
 cs

 

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
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
char arr[16];
char ans[16];
int l, c;
// 모음 최소 1개
// 자음 최소 2개
void dfs(int idx, int step) {
if (step == l) {
    int cnt1 = 0, cnt2 = 0;
    rep(i, l) {
        if (ans[i] == 'a' || ans[i] == 'e' || ans[i] == 'i' || ans[i] == 'o' || ans[i] == 'u')
            cnt1++;
        else
            cnt2++;
        // 조건 만족하면 바로 출력
        if (cnt1 >= 1 && cnt2 >= 2) {
            rep(i, l)
                cout << ans[i];
            cout << '\n';
            return;
        }
    }
    return;
}
    for (int i = idx; i < c; i++) {
        ans[step] = arr[i];
        dfs(i + 1, step + 1);
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> l >> c;
    rep(i, c)
        cin >> arr[i];
    sort(arr, arr + c);
    dfs(0, 0);
}
cs
반응형

'백준 > 백트래킹' 카테고리의 다른 글

백준 10819  (0) 2021.02.03
백준 1987  (0) 2021.02.03
백준 1182  (0) 2021.01.30
백준 6603  (0) 2021.01.30
백준 9663  (0) 2021.01.26
반응형

www.acmicpc.net/problem/1182

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

 

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>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int arr[21];
int n, s;
int cnt;
int sum = 0;
int ans = 0;
 void dfs(int idx, int step) {
     // r개 만큼 선택 했으면
    if (step == cnt) {
        if (sum == s)
            ans++;
        return;
    }
    
    // 백트래킹
    // 선택하고 되돌려놓기
    for (int i = idx; i < n; i++) {
        sum += arr[i];
        dfs(i + 1, step + 1);
        sum -= arr[i];
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> s;
    rep(i, n)
        cin >> arr[i];
    
    // n개 중 r개 고를 때 r값 결정
// 1부터 n까지 다 해봐야 함
    for (int i = 1; i <= n; i++) {
        cnt = i;
        dfs(0, 0);
        sum = 0;
    }
    cout << ans;
}
 cs
반응형

'백준 > 백트래킹' 카테고리의 다른 글

백준 10819  (0) 2021.02.03
백준 1987  (0) 2021.02.03
백준 1759  (0) 2021.02.03
백준 6603  (0) 2021.01.30
백준 9663  (0) 2021.01.26
반응형

www.acmicpc.net/problem/6603

 

6603번: 로또

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로

www.acmicpc.net

 

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
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int arr[13];
int val[13];
int k;
void dfs(int idx, int cnt) {
    // 종료 조건
    if (cnt == 6) {
        rep(i,6)
            cout << val[i] << ' ';
        cout << '\n';
        return;
    }
    
    // 백트래킹
    // n개 중 6개 뽑아서 나열
    for (int i = idx; i < k; i++) {
        // 현재 값을 배열에 저장
        // cnt는 배열의 인덱스로 사용
        val[cnt] = arr[i];
        dfs(i+1, cnt + 1);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> k;
    while (k != 0) {
        rep(i, k)
            cin >> arr[i];
 
        dfs(0, 0);
        cout << '\n';
        cin >> k;
    }
}
cs
반응형

'백준 > 백트래킹' 카테고리의 다른 글

백준 10819  (0) 2021.02.03
백준 1987  (0) 2021.02.03
백준 1759  (0) 2021.02.03
백준 1182  (0) 2021.01.30
백준 9663  (0) 2021.01.26
반응형

www.acmicpc.net/problem/1520

 

1520번: 내리막 길

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으

www.acmicpc.net

BFS -> 시간 초과

DFS + DP로 풀어야 함

dp[i][j] = -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
#include <iostream>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int m, n;
int arr[501][501];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
int dp[501][501];
int dfs(int x, int y) {
    if (x == (m - 1) && y == (n - 1))
        return 1;
 
    // -1: 방문 안 한 상태
    if (dp[x][y] == -1) {
        // 0: 방문 한 상태
        dp[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (arr[nx][ny] < arr[x][y])
                    dp[x][y] += dfs(nx, ny);
            }
        }
    }
    
    return dp[x][y];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp, -1, sizeof(dp));
    cin >> m >> n;
    rep(i, m) {
        rep(j, n)
            cin >> arr[i][j];
    }
    cout << dfs(0, 0);
}
 cs

 

반응형

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

백준 11052  (0) 2021.02.15
백준 9095  (0) 2021.02.15
백준 2579  (0) 2021.01.28
백준 2565  (0) 2021.01.28
백준 9251  (0) 2021.01.27
반응형

www.acmicpc.net/problem/14889

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

 
1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int now, int cnt) {
    if (cnt == n / 2) {
        // 로직 처리
        return;
    }
 
    // 조합 찾기(n개 중 r개)
    for (int i = now; i < n; i++) {
        visited[i] = true;
        dfs(i + 1, cnt + 1);
        visited[i] = false;
    }
}
 cs

 

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>
#include <algorithm>
using namespace std;
int n;
int arr[21][21];
int visited[20];
int min_gap = 987654321;
void dfs(int now, int cnt) {
    if (cnt == n / 2) {
        int score1 = 0;
        int score2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 선택됨 -> 팀1
                if (visited[i] && visited[j])
                    score1 += (arr[i][j] + arr[j][i]);
                // 선택안됨 -> 팀2
                else if (!visited[i] && !visited[j])
                    score2 += (arr[i][j] + arr[j][i]);
            }
        }
        min_gap = min(min_gap, abs(score1 - score2));
        return;
    }
 
    // 조합 찾기(n개 중 r개)
    for (int i = now; i < n; i++) {
        visited[i] = true;
        dfs(i + 1, cnt + 1);
        visited[i] = false;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) 
            cin >> arr[i][j];
    }
    
    dfs(0, 0);
    cout << min_gap;
}
 cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 14500  (0) 2021.02.13
백준 15686  (0) 2021.02.05
백준 14502  (0) 2021.02.03
백준 15684  (0) 2021.02.03
백준 14888  (0) 2021.01.28
반응형

www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

 

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
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int n;
int arr[11];
int op[4];
int op_arr[10];
int max_val = -987654321;
int min_val = 987654321;
stack<int> s;
stack<int> temp;
void insertData() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    for (int i = 0; i < 4; i++)
        cin >> op[i];
}
void initData() {
    for (int i = n - 1; i >= 0; i--)
        temp.push(arr[i]);
 
    int idx = 0;
    for (int i = 0; i < 4; i++) {
        while (op[i] > 0) {
            op_arr[idx++] = i;
            op[i]--;
        }
    }
}
void func() {
    s = temp;
    int op_idx = 0;
    while (s.size() > 1) {
        int result;
        int a = s.top();
        s.pop();
        int b = s.top();
        s.pop();
        if (op_arr[op_idx] == 0)
            result = a + b;
        else if (op_arr[op_idx] == 1)
            result = a - b;
        else if (op_arr[op_idx] == 2)
            result = a * b;
        else if (op_arr[op_idx] == 3)
            result = a / b;
        s.push(result);
        op_idx++;
    }
    int ret = s.top();
    s.pop();
    min_val = min(min_val, ret);
    max_val = max(max_val, ret);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    insertData();
    initData();
 
    func();
    while (next_permutation(op_arr, op_arr + (n - 1))) 
        func();
    cout << max_val << '\n' << min_val;
}
 
 cs

 

백트래킹 사용

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
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int n;
int arr[11];
int op[4];
int max_val = -987654321;
int min_val = 987654321;
 
// cnt: 연산 횟수
void dfs(int temp_val, int cnt) {
    if (cnt == n - 1) {
        min_val = min(min_val, temp_val);
        max_val = max(max_val, temp_val);
        return;
    }
 
    // 백트래킹 부분
    for (int i = 0;i < 4;i++) {        
        if (op[i] != 0) {
            --op[i];            // 사용한 연산자는 개수 빼야함
            if (i == 0) 
                dfs(temp_val + arr[cnt + 1], cnt+1);
            else if(i == 1)
                dfs(temp_val - arr[cnt + 1], cnt + 1);
            else if (i == 2)
                dfs(temp_val * arr[cnt + 1], cnt + 1);
            else if (i == 3)
                dfs(temp_val / arr[cnt + 1], cnt + 1);
            ++op[i];            // 다음 탐색을 위해서 연산자 개수 복구
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    for (int i = 0; i < 4; i++)
        cin >> op[i];
    dfs(arr[0], 0);
    cout << max_val << '\n' << min_val;
}
 
 cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 14500  (0) 2021.02.13
백준 15686  (0) 2021.02.05
백준 14502  (0) 2021.02.03
백준 15684  (0) 2021.02.03
백준 14889  (0) 2021.01.29

+ Recent posts

티스토리툴바