반응형

www.acmicpc.net/problem/16929

 

16929번: Two Dots

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

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
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, m;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int visited[50][50];
char arr[50][50];
void dfs(int x, int y, char c, int ban_direc) {
    // 방문한 곳 또 방문했으면 성공
    if (visited[x][y]) {
        cout << "Yes";
        exit(0);
    }
    visited[x][y] = 1;
 
    rep(i, 4) {
        // 반대 방향으로 못 가도록 설정
        if (i == ban_direc) continue;
 
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && c == arr[nx][ny]) {
            // 이동하면 안되는 방향 설정 (현재와 반대 방향)
            int ban = 0;
            if (i == 0) ban = 1;
            else if (i == 1) ban = 0;
            else if (i == 2) ban = 3;
            else if (i == 3) ban = 2;
            dfs(nx, ny, arr[nx][ny], ban);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    rep(i, n) {
        rep(j, m)
            cin >> arr[i][j];
    }
    rep(i, n) {
        rep(j, m) {
            if (!visited[i][j])
                dfs(i, j, arr[i][j], 0);    // (row, col, 현재문자, 이동 금지 방향)
        }
    }
    cout << "No";
}
 cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 12946 [복습 필수]  (0) 2021.03.11
백준 16940 [복습 필수]  (0) 2021.03.10
백준 16947 [복습 필수]  (0) 2021.03.06
백준 16197  (0) 2021.02.23
백준 13549  (0) 2021.02.19
반응형

www.acmicpc.net/problem/16947

 

16947번: 서울 지하철 2호선

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호

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
int dfs(int now, int before) {
    if (visited[now] == 1)    // 사이클 찾았으면
        return now;            // 현재 노드 리턴
    visited[now] = 1;        // 방문 처리
 
    for (int next : v[now]) {            // 연결된 노드 탐색
        if (next == before) continue;    // 바로 전으로 돌아가면 패스
 
        ret = dfs(next, now);            // 다음 탐색
 
        if (ret > 0) {                // 사이클 시작점 찾았으면
            visited[now] = 2;        // 사이클에 포함 시킴
 
            if (now == ret)            // 사이클 시작점까지 도착 -> 나머지는 사이클에 포함 안됨
                return -1;                    //   -> -1 리턴
            else 
                return ret;            // 사이클 시작점
        }
 
        if (ret == -1)
            return -1;
    }
    return 0;        // 못찾았으면 0 리턴
}
 cs

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
rep(i,n) {
    if (visited[i] == 2) {    // 사이클에 포함된 경우
        dist[i] = 0;        // 사이클과의 거리는 0
        q.push(i);
    }
    else
        dist[i] = -1;        // 사이클에 포함 안되면 -1
}
 
while (!q.empty()) {    // bfs로 사이클과의 거리를 구함
    int now = q.front();
    q.pop();
    for(int next : v[now]) {
        if (dist[next] == -1) {    // 다음 노드가 사이클에 포함되어있지 않다면
            q.push(next);
            dist[next] = dist[now] + 1;
        }
    }
}
 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
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
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
vector<vector<int> > v;
int n, a, b;
int visited[3001];    // 0: not visited, 1: visited, 2: cycle
int dist[3001];        // 사이클로부터의 거리
int ret;
int dfs(int now, int before) {
    if (visited[now] == 1)    // 사이클 찾았으면
        return now;            // 현재 노드 리턴
    visited[now] = 1;        // 방문 처리
 
    for (int next : v[now]) {            // 연결된 노드 탐색
        if (next == before) continue;    // 바로 전으로 돌아가면 패스
 
        ret = dfs(next, now);            // 다음 탐색
 
        if (ret > 0) {                // 사이클 시작점 찾았으면
            visited[now] = 2;        // 사이클에 포함 시킴
 
            if (now == ret)            // 사이클 시작점까지 도착 -> 나머지는 사이클에 포함 안됨
                return -1;                    //   -> -1 리턴
            else 
                return ret;            // 사이클 시작점
        }
 
        if (ret == -1)
            return -1;
    }
    return 0;        // 못찾았으면 0 리턴
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    v.resize(n + 1);
    fill(dist, dist + n + 1, 987654321);
 
    rep(i, n) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    dfs(1, -1);
    queue<int> q;
    rep(i,n) {
        if (visited[i] == 2) {    // 사이클에 포함된 경우
            dist[i] = 0;        // 사이클과의 거리는 0
            q.push(i);
        }
        else
            dist[i] = -1;        // 사이클에 포함 안되면 -1
    }
 
    while (!q.empty()) {    // bfs로 사이클과의 거리를 구함
        int now = q.front();
        q.pop();
        for(int next : v[now]) {
            if (dist[next] == -1) {    // 다음 노드가 사이클에 포함되어있지 않다면
                q.push(next);
                dist[next] = dist[now] + 1;
            }
        }
    }
 
    rep(i,n)
        cout << dist[i] << ' ';
}
 cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 16940 [복습 필수]  (0) 2021.03.10
백준 16929  (0) 2021.03.06
백준 16197  (0) 2021.02.23
백준 13549  (0) 2021.02.19
백준 14226 [복습 필수]  (0) 2021.02.19
반응형

www.acmicpc.net/problem/12100

 

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

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
// 한 쪽으로 옮기기
void move() {
    int temp[21][21];
    // 열 단위(세로줄)로 처리
    rep(j, n) {
        bool flag = 0;    // 합칠 수 있는가?
        int row = -1;    // temp[][]의 현재 row
        rep(i, n) {
            if (arr[i][j] == 0) continue;
            if (flag && arr[i][j] == temp[row][j]) {    // 합칠 수 있음 + arr[i] == temp[row]
                temp[row][j] *= 2;                        // 현재 row에서 합치기
                flag = 0;                                // 합칠 수 없도록 변경
            }
            else {
                temp[++row][j] = arr[i][j];                // 현재 row에서 못 합치므로, 다음 row로 이동
                flag = 1;                                // 합칠 수 있도록 변경
            }
        }
 
        for (int k = row + 1; k < n; k++)                // 빈 칸 채우기
            temp[k][j] = 0;
            
    }
 
    rep(i, n) {
        rep(j, n)
            arr[i][j] = temp[i][j];
    }
}
 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
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
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, ans;
struct board {
    int arr[21][21];
    
    // 90도 회전
    void rotate() {
        int temp[21][21];
        rep(i, n) {
            rep(j, n)
                temp[i][j] = arr[n - j - 1][i];
        }
 
        rep(i, n) {
            rep(j, n)
                arr[i][j] = temp[i][j];
        }
    }
 
    // 한 쪽으로 옮기기
    void move() {
        int temp[21][21];
        // 열 단위(세로줄)로 처리
        rep(j, n) {
            bool flag = 0;    // 합칠 수 있는가?
            int row = -1;    // temp[][]의 현재 row
            rep(i, n) {
                if (arr[i][j] == 0) continue;
                if (flag && arr[i][j] == temp[row][j]) {    // i: 계속 증가, row: 조건 맞으면 증가
                    temp[row][j] *= 2;                        // 현재 row에서 합치기
                    flag = 0;
                }
                else {
                    temp[++row][j] = arr[i][j];                // 현재 row에서 못 합치므로, 다음 row로 이동
                    flag = 1;
                }
            }
 
            for (int k = row + 1; k < n; k++)                // 빈 칸 채우기
                temp[k][j] = 0;
            
        }
 
        rep(i, n) {
            rep(j, n)
                arr[i][j] = temp[i][j];
        }
    }
 
    // 최댓값
    int getMax() {
        int ret = 0;
        rep(i, n) {
            rep(j, n)
                ret = max(ret, arr[i][j]);
        }
        return ret;
    }
};
 
void dfs(board b, int cnt) {
    if (cnt == 5) {
        ans = max(ans, b.getMax());
        return;
    }
 
    rep(i, 4) {
        // 원본을 이동시키면 안됨
        board next = b;
        next.move();
        dfs(next, cnt + 1);
        // 원본 회전시키기
        b.rotate();
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    board b;
    cin >> n;
    rep(i, n) {
        rep(j, n)
            cin >> b.arr[i][j];
    }
    dfs(b, 0);
    cout << ans;
}
 cs
반응형

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

백준 3190  (0) 2021.04.29
백준 13460  (0) 2021.03.07
백준 20055  (0) 2021.02.23
백준 15685 [복습 필수]  (0) 2021.02.23
백준 14503  (0) 2021.02.22
반응형

www.acmicpc.net/problem/2580

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int arr[10][10], cnt;
bool row_visited[10][10], col_visited[10][10], sqr_visited[10][10];
// 핵심
// 1. visited 검사
// 2. 백트래킹 종료 조건
int getSqrNum(int x, int y) {
    x -= x % 3;
    y -= y % 3;
    if (x == 0) {
        if (y == 0) return 0;
        if (y == 3) return 1;
        if (y == 6) return 2;
    }
    if (x == 3) {
        if (y == 0) return 3;
        if (y == 3) return 4;
        if (y == 6) return 5;
    }
    if (x == 6) {
        if (y == 0) return 6;
        if (y == 3) return 7;
        if (y == 6) return 8;
    }
}
void setVisited(int i, int j, bool flag) {
    row_visited[i][arr[i][j]] = flag;
    col_visited[j][arr[i][j]] = flag;
    sqr_visited[getSqrNum(i, j)][arr[i][j]] = flag;
}
bool chk(int x, int y, int val) {
    if (row_visited[x][val]) return false;    // 가로 검사
    if (col_visited[y][val]) return false;    // 세로 검사
    
    x -= x % 3;                                // 사각형 검사
    y -= y % 3;
    if (sqr_visited[getSqrNum(x, y)][val]) return false;
    return true;
}
void print() {
    rep(i, 9) {
        rep(j, 9)
            cout << arr[i][j] << ' ';
        cout << '\n';
    }
}
void dfs(int x, int y) {
    // 0 전부 없어졌으면 출력
    if (cnt == 0) {
        print();
        exit(0);
    }
 
    // 백트래킹
    for (int i = x; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (arr[i][j] == 0) {                // 0이면
                int k;
                for (k = 1; k <= 9; k++) {        // 1 ~ 9 다 넣어봄
                    if (chk(i, j, k)) {            // 조건 맞으면 다음 단계 진행
                        arr[i][j] = k;
                        setVisited(i, j, 1);
                        cnt--;                    // 0 개수 줄이기
                        dfs(i, j+1);
                        cnt++;
                        setVisited(i, j, 0);
                        arr[i][j] = 0;            // 다시 0으로 돌리기
                    }
                }
                if (k == 10) return;            // k == 10 -> 0인 칸에 숫자 넣지 못하고 반복문 끝남
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    rep(i, 9) {
        rep(j, 9) {
            cin >> arr[i][j];
            if (arr[i][j] != 0)
                setVisited(i, j, 1);            // visited 설정
            else
                cnt++;                            // 0 개수 체크
        }
    }
    dfs(0, 0);
}
cs
반응형

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

백준 1062  (0) 2021.03.07
N-Queen 복습 (백준 9663)  (0) 2021.02.23
백준 16198  (0) 2021.02.23
백준 15658  (0) 2021.02.23
백준 1248 [복습 필수]  (0) 2021.02.15
반응형

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
#include <iostream>
using namespace std;
int n, ans;
int visited[15][15];
int col_visited[15];
bool chk(int x, int y) {
    int i = x+1;
    int j = y+1;
    while (i >= 0 && i < n && j >= 0 && j < n) {    // 우하 대각선
        if (visited[i++][j++])
            return false;
    }
    i = x+1;
    j = y-1;
    while (i >= 0 && i < n && j >= 0 && j < n) {    // 좌하 대각선
        if (visited[i++][j--])
            return false;
    }
    i = x-1;
    j = y+1;
    while (i >= 0 && i < n && j >= 0 && j < n) {    // 우상 대각선
        if (visited[i--][j++])
            return false;
    }
 
    i = x-1;
    j = y-1;
    while (i >= 0 && i < n && j >= 0 && j < n) {    // 좌상 대각선
        if (visited[i--][j--])
            return false;
    }
    return true;
}
void bfs(int row) {
    if (row == n) {
        ans++;
        return;
    }
    int j;
    for (int i = row; i < n; i++) {
        for (j = 0; j < n; j++) {
            // 세로 검사 && 대각선 검사
            if (!col_visited[j] && chk(i,j)) {
                col_visited[j] = 1;        // 열 방문 처리    
                visited[i][j] = 1;        // 퀸 놓음
                bfs(row + 1);
                visited[i][j] = 0;    
                col_visited[j] = 0;
            }
        }
        // 퀸 놓을 공간 없어서 다음 단계 진행 못하고 j가 끝까지 감
        if (j == n)
            return;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    bfs(0);
    cout << ans;
}
 cs
반응형

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

백준 1062  (0) 2021.03.07
백준 2580  (0) 2021.02.24
백준 16198  (0) 2021.02.23
백준 15658  (0) 2021.02.23
백준 1248 [복습 필수]  (0) 2021.02.15
반응형

www.acmicpc.net/problem/16197

 

16197번: 두 동전

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고,

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <queue>
#define pii pair<int, int>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, m;
char arr[21][21];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
bool visited[20][20][20][20];
queue<pii> q;
void bfs() {
    int cnt = 1;
    while (!q.empty()) {
        int size = q.size() / 2;    // 한 번에 두 개 꺼냄
        while (size--){
            if (cnt > 10)            // 10번 초과하면 불가
                return;
            pii c1 = q.front();
            q.pop();
            pii c2 = q.front();
            q.pop();
 
            if (c1 == c2)            // 두 동전이 겹치면 패스
                continue;
 
            rep(i, 4) {
                int nx1 = c1.first + dx[i];
                int ny1 = c1.second + dy[i];
                int nx2 = c2.first + dx[i];
                int ny2 = c2.second + dy[i];
 
                bool drop1 = false;
                bool drop2 = false;
                if (nx1 < 0 || nx1 >= n || ny1 < 0 || ny1 >= m)
                    drop1 = true;
                if (nx2 < 0 || nx2 >= n || ny2 < 0 || ny2 >= m)
                    drop2 = true;
 
                if (drop1 && drop2)    // 둘 다 떨어지면 패스
                    continue;
 
                else if ((drop1 && !drop2) || (!drop1 && drop2)) {    // 하나만 떨어짐
                    cout << cnt;
                    exit(0);
                }
 
                if (arr[nx1][ny1] == '#' && arr[nx2][ny2] == '#') continue; // 둘 다 벽이면 패스
 
                if (arr[nx1][ny1] != '#' && arr[nx2][ny2] != '#') {            // 둘 다 벽 아니면 이동
                    if (!visited[nx1][ny1][nx2][ny2]) {
                        q.push({ nx1, ny1 });
                        q.push({ nx2, ny2 });
                        visited[nx1][ny1][nx2][ny2] = 1;
                    }
                }
                else if(arr[nx1][ny1] == '#' && arr[nx2][ny2] != '#') {        // 둘 중 하나가 벽이면
                    if (!visited[c1.first][c1.second][nx2][ny2]) {            
                        q.push(c1);                                            // 벽이면 제자리 삽입
                        q.push({ nx2, ny2 });                                // 벽 아니면 다음 위치 삽입
                        visited[c1.first][c1.second][nx2][ny2] = 1;
                    }
                }
                else if (arr[nx1][ny1] != '#' && arr[nx2][ny2] == '#') {
                    if (!visited[nx1][ny1][c2.first][c2.second]) {
                        q.push({ nx1, ny1 });
                        q.push(c2);
                        visited[nx1][ny1][c2.first][c2.second] = 1;
                    }
                }
                    
            }
        }
        cnt++;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    rep(i, n) {
        rep(j, m) {
            cin >> arr[i][j];
            if (arr[i][j] == 'o') 
                q.push({ i, j });
        }
    }
    if (q.size() == 1) {    // 입력된 동전 위치가 하나 -> 두 개의 동전이 겹침
        cout << -1;
        exit(0);
    }
    bfs();
    cout << -1;
}
cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 16929  (0) 2021.03.06
백준 16947 [복습 필수]  (0) 2021.03.06
백준 13549  (0) 2021.02.19
백준 14226 [복습 필수]  (0) 2021.02.19
백준 13913  (0) 2021.02.19
반응형

www.acmicpc.net/problem/16198

 

16198번: 에너지 모으기

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있

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
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, arr[11], ans;
bool visited[11];
// idx 양 옆 숫자 선택
int calc(int idx) {
    int ret = 0;
    for (int i = idx - 1; i >= 0; i--) {    // 0 아닌 숫자 나올 때까지 왼쪽으로 이동
        if (arr[i] != 0) {
            ret += arr[i];
            break;
        }
    }
    for (int i = idx + 1; i < n; i++) {        // 0 아닌 숫자 나올 때까지 오른쪽으로 이동
        if (arr[i] != 0) {
            ret *= arr[i];
            break;
        }
    }
    return ret;
}
void bfs(int cnt, int sum) {
    if (cnt == n-1) {
        ans = max(ans, sum);
        return;
    }
    // 0 / 1 ~ n-2 / n-1 선택
    for (int i = 1; i <= n-2; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            int temp = arr[i];
            arr[i] = 0;                    // 선택한 숫자를 0으로 변경
            bfs(cnt+1, sum+calc(i));    // 계산 후에 다음 단계 진행
            arr[i] = temp;
            visited[i] = 0;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, n)
        cin >> arr[i];
    bfs(1, 0);
    cout << ans;
}
cs
반응형

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

백준 2580  (0) 2021.02.24
N-Queen 복습 (백준 9663)  (0) 2021.02.23
백준 15658  (0) 2021.02.23
백준 1248 [복습 필수]  (0) 2021.02.15
백준 2529  (0) 2021.02.15
반응형

www.acmicpc.net/problem/15658

 

15658번: 연산자 끼워넣기 (2)

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 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
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, arr[12], op[50];
int max_val = -987654321, min_val = 987654321;
// 연산자 모두 나열: +(1) +(2) + (3) / +(2) +(1) +(3) / +(1) +(3) +(2) 모두 다른 경우로 인식
// 연산자 남아있는 개수를 확인해서 탐색하는 방식으로 해야함
void func(int step, int val) {
    if (step == n) {
        max_val = max(max_val, val);
        min_val = min(min_val, val);
        return;
    }
    rep (i, 4) {
        if (op[i]>0) {        // 현재 연산자 남아있으면
            op[i]--;        // 하나 사용
            int temp = 0;
            if (i == 0)
                temp = val + arr[step];
            else if (i == 1)
                temp = val - arr[step];
            else if (i == 2)
                temp = val * arr[step];
            else if (i == 3)
                temp = val / arr[step];
            func(step + 1, temp);    // 다음 숫자 계산
            op[i]++;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, n)
        cin >> arr[i];
 
    rep(i, 4)
        cin >> op[i];
    func(1, arr[0]);
    cout << max_val << '\n' << min_val;
}
 cs
반응형

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

N-Queen 복습 (백준 9663)  (0) 2021.02.23
백준 16198  (0) 2021.02.23
백준 1248 [복습 필수]  (0) 2021.02.15
백준 2529  (0) 2021.02.15
백준 15661  (0) 2021.02.15

+ Recent posts

티스토리툴바