반응형

www.acmicpc.net/problem/18290

 

18290번: NM과 K (1)

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, k, arr[11][11];
int visited[11][11];
// 모든 숫자가 음수일 수도 있으므로 -987654321으로 초기화
int ans = -987654321, temp = 0;
vector<pair<int, int> > v;
void visit(int i, int j, int state) {
    if (state == 1) {
        // 겹치는 영역이 두 개 이상일 수도 있으므로 visited[][]=1이 아닌 visited[][]++
        visited[i][j]++;
        if (i - 1 >= 0) visited[i - 1][j]++;
        if (j - 1 >= 0) visited[i][j - 1]++;
        if (i + 1 < n) visited[i + 1][j]++;
        if (j + 1 < m) visited[i][j + 1]++;
    }
    else {
        visited[i][j]--;
        if (i - 1 >= 0) visited[i - 1][j]--;
        if (j - 1 >= 0) visited[i][j - 1]--;
        if (i + 1 < n) visited[i + 1][j]--;
        if (j + 1 < m) visited[i][j + 1]--;
    }
}
void dfs(int x, int y, int cnt) {
    if (cnt == k) {
        ans = max(ans, temp);
        return;
    }
    for (int i = x; i < n;i++) {
        y = 0;
        for (int j = y; j < m;j++) {
            if (visited[i][j]==0) {
                visit(i, j, 1);
                temp += arr[i][j];
                v.push_back({ i,j });
                dfs(i, j, cnt + 1);
                v.erase(v.end() - 1);
                temp -= arr[i][j];
                visit(i, j, 0);
            }
        }
        
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++)
            cin >> arr[i][j];
    }
    dfs(0, 0, 0);
    cout << ans;
}
cs
반응형

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

백준 2529  (0) 2021.02.15
백준 15661  (0) 2021.02.15
백준 10971  (0) 2021.02.03
백준 10819  (0) 2021.02.03
백준 1987  (0) 2021.02.03
반응형

www.acmicpc.net/problem/10971

 

10971번: 외판원 순회 2

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j

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>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, ans, arr[11][11];
int idx_arr[11];    // 탐색 순서 저장
 
int calc() {
    int ret = 0;
    for (int i = 0;i < n - 1;i++){
        // 0이면 못감
        if (arr[idx_arr[i]][idx_arr[i + 1]] == 0)
            return 987654321;
 
        // 다음 도시로 이동
        ret += arr[idx_arr[i]][idx_arr[i + 1]];
    }
    // 0이면 못감
    if (arr[idx_arr[n - 1]][idx_arr[0]] == 0)
        return 987654321;
 
    // 마지막 도시 -> 처음 도시
    ret += arr[idx_arr[n - 1]][idx_arr[0]];
    return ret;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, n) {
        idx_arr[i] = i;
        rep(j, n)
            cin >> arr[i][j];
    }
    ans = calc();
    while (next_permutation(idx_arr, idx_arr + n))
        ans = min(ans, calc());
    cout << ans;
}
cs
반응형

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

백준 15661  (0) 2021.02.15
백준 18290  (0) 2021.02.15
백준 10819  (0) 2021.02.03
백준 1987  (0) 2021.02.03
백준 1759  (0) 2021.02.03
반응형

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

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

백트래킹: DFS + 가지치기

 

1. 현재 위치에 퀸 놓을 수 있는지 없는지 검사

2. 현재 위치에 말을 놓을 수 있다면, 현재 위치가 마지막 줄인지 검사

  1) 마지막 줄이면 return 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
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 <cstring>
using namespace std;
 
int n;
int x_pos[16];
int y_pos[16];
int dfs(int x, int y) {
    // 1. 조건 검사 (현재까지 진행된 라인까지만 검사)
    for (int i = 0; i < x; i++) {
        // i번째 줄의 x 좌표와 현재 x 좌표가 같다면
        if (x_pos[i] == x)
            return 0;
        // i번째 줄의 y 좌표와 현재 y 좌표가 같다면
        if (y_pos[i] == y)
            return 0;
        // i번째 줄의 대각선 위치가 같다면
        // 대각선일 경우 x, y좌표 위치가 동일하게 증가(감소)함
        // (x 좌표 변화량 == y 좌표 변화량) -> 같은 대각선 상에 있음
        if (abs(x - x_pos[i]) == abs(y - y_pos[i]))
            return 0;
    }
 
    // 2. 제일 아랫줄 도착
    if (x == n-1)
        return 1;
    
    // 3. 현재 말의 위치 저장
    // x번째 줄에서의 좌표(x,y) 저장
    x_pos[x] = x, y_pos[x] = y;
 
    int cnt = 0;
    // 4. 다음 라인 탐색
    for (int i = 0; i < n; i++) {
        cnt += dfs(x + 1, i);
    }
    return cnt;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        ans += dfs(0, i);
    }
    cout << ans;
}
 cs

참고: www.youtube.com/watch?v=ltm-JX5R1pA

반응형

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

백준 10819  (0) 2021.02.03
백준 1987  (0) 2021.02.03
백준 1759  (0) 2021.02.03
백준 1182  (0) 2021.01.30
백준 6603  (0) 2021.01.30

+ Recent posts

티스토리툴바