반응형

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
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int arr[21];
int n, s, sum, ans = 0;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> s;
    rep(i, n)
        cin >> arr[i];
    
    int mask = 1;
    while (mask < (1 << n)) {
        sum = 0;
        for (int i = 0;i < n;i++)
            sum += arr[i] * ((mask >> i) & 1);
        if (sum == s)
            ans++;
        mask++;
    }
    cout << ans;
}
cs
반응형

'백준 > 브루트포스' 카테고리의 다른 글

백준 14225  (0) 2021.02.23
백준 14391  (0) 2021.02.15
백준 6064  (0) 2021.02.13
백준 1107 [복습 필수]  (0) 2021.02.13
백준 1476  (0) 2021.02.13
반응형

www.acmicpc.net/problem/1248

 

1248번: 맞춰봐

첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-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
#include <iostream>
#include <string>
using namespace std;
int n;
char s[11][11];
int sum[11];
int arr[11][11];
string str;
bool valid(int col) {
    if (col == 1)
        return true;
    for (int row = 1; row <= col; row++) {
        int cur = arr[col][col] + arr[row][col - 1];
        if (s[row][col] == '+' && cur <= 0)
            return false;
        else if (s[row][col] == '-' && cur >= 0)
            return false;
        else if (s[row][col] == '0' && cur != 0)
            return false;
        arr[row][col] = cur;
    }
    return true;
}
void dfs(int cnt) {
    // 출력
    if (cnt > n) {
        for (int i = 1; i <= n; i++)
            cout << arr[i][i] << ' ';
        exit(0);
    }
 
    // 1부터 n까지 숫자를 모두 다 고른 다음에 검사, 출력하면 시간 초과
    // 한 라인 추가할 때마다 검사, 해당 라인 통과 못하면 그 다음 라인은 아예 검사 안함
    char now = s[cnt][cnt];
    if (now == '+') {
        for (int i = 1; i <= 10; i++) {
            arr[cnt][cnt] = i;
            if(valid(cnt))
                dfs(cnt + 1);
        }
    }
    else if (now == '-') {
        for (int i = 1; i <= 10; i++) {
            arr[cnt][cnt] = -i;
            if (valid(cnt))
                dfs(cnt + 1);
        }
    }
    else if (now == '0') {
        arr[cnt][cnt] = 0;
        if (valid(cnt))
            dfs(cnt + 1);
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = i;j <= n;j++)
            cin >> s[i][j];
    }
    dfs(1);
}
 cs
반응형

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

백준 16198  (0) 2021.02.23
백준 15658  (0) 2021.02.23
백준 2529  (0) 2021.02.15
백준 15661  (0) 2021.02.15
백준 18290  (0) 2021.02.15
반응형

www.acmicpc.net/problem/2529

 

2529번: 부등호

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제

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
#include <iostream>
#include <algorithm>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n;
char arr[10];
int visited[10];
int num_arr[10];
int max_arr[10];
int min_arr[10];
ll ans_max = -9999999999, ans_min = 9999999999, temp;
void dfs(int num, int idx, int cnt) {
    temp = 0;
    if (idx==n) {
        rep(i, cnt) {
            temp = temp * 10 + num_arr[i];
        }
        if (temp > ans_max) {
            ans_max = temp;
            rep(i, n+1)
                max_arr[i] = num_arr[i];
        }
        if (temp < ans_min) {
            ans_min = temp;
            rep(i, n+1)
                min_arr[i] = num_arr[i];
        }
        return;
    }
 
    if (arr[idx] == '>') {
        for (int i = num - 1; i >= 0;i--) {
            if (!visited[i]) {
                visited[i] = 1;
                num_arr[cnt] = i;
                dfs(i, idx + 1, cnt + 1);
                visited[i] = 0;
            }
        }
    }
    else {
        for (int i = num + 1; i <= 9; i++) {
            if (!visited[i]) {
                visited[i] = 1;
                num_arr[cnt] = i;
                dfs(i, idx + 1, cnt + 1);
                visited[i] = 0;
            }
        }
    }
}
int main() {
    cin >> n;
    rep(i, n)
        cin >> arr[i];
    rep(i, 10) {
        visited[i] = 1;
        num_arr[0] = i;
        dfs(i, 0, 1);
        visited[i] = 0;
    }
    rep(i, n+1)
        cout << max_arr[i];
    cout << '\n';
    rep(i, n+1)
        cout << min_arr[i];
}
cs
반응형

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

백준 15658  (0) 2021.02.23
백준 1248 [복습 필수]  (0) 2021.02.15
백준 15661  (0) 2021.02.15
백준 18290  (0) 2021.02.15
백준 10971  (0) 2021.02.03
반응형

www.acmicpc.net/problem/15661

 

15661번: 링크와 스타트

첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100

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
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, arr[21][21], ans = 987654321;
int visited[21];
vector<int> v1, v2;
int team1, team2;
void dfs(int now) {
    v1.clear();
    v2.clear();
    team1 = 0;
    team2 = 0;
    // 계산
    rep(i, n) {
        if (visited[i])
            v1.push_back(i);
        else
            v2.push_back(i);
    }
    if (v1.size() == 1)
        team1 = 0;
    else {
        for (int i : v1) {
            for (int j : v1) {
                if (i == j) continue;
                team1 += arr[i][j];
            }
        }
    }
    if (v2.size() == 1)
        team2 = 0;
    else {
        for (int i : v2) {
            for (int j : v2) {
                if (i == j) continue;
                team2 += arr[i][j];
            }
        }
    }
    ans = min(ans, abs(team1 - team2));
    // 백트래킹
    for (int i = now; i <= n; i++) {
        visited[i] = 1;
        dfs(i + 1);
        visited[i] = 0;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, n) {
        rep(j, n)
            cin >> arr[i][j];
    }
    visited[1] = 1;
    dfs(2);
    cout << ans;
}
 cs

비슷한 문제: rltn2121.tistory.com/15

반응형

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

백준 1248 [복습 필수]  (0) 2021.02.15
백준 2529  (0) 2021.02.15
백준 18290  (0) 2021.02.15
백준 10971  (0) 2021.02.03
백준 10819  (0) 2021.02.03
반응형

www.acmicpc.net/problem/14501

 

14501번: 퇴사

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

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
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;i++)
#define pii pair<int, int>
using namespace std;
int n, ans = -1;
pii arr[16];
void dfs(int now, int sum) {
    ans = max(ans, sum);
    for (int i = now; i <= n; i++) {                    // 모든 날짜 다 탐색
        if (i + arr[i].first <= n+1)                    // 현재 상담이 n+1일 안에 끝나면
            dfs(i + arr[i].first, sum + arr[i].second);    // 그 날짜로 이동, 돈 더함
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, n)
        cin >> arr[i].first >> arr[i].second;
    dfs(1, 0);
    cout << ans;
}
 cs
반응형

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

백준 14890  (0) 2021.02.21
백준 14499  (0) 2021.02.21
백준 14500  (0) 2021.02.13
백준 15686  (0) 2021.02.05
백준 14502  (0) 2021.02.03
반응형

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

 

9095번: 1, 2, 3 더하기

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int t, n, dp[12];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i < 11; i++)
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n] << '\n';
    }
}
cs
반응형

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

백준 15990  (0) 2021.02.15
백준 11052  (0) 2021.02.15
백준 1520 [복습 필수]  (0) 2021.01.30
백준 2579  (0) 2021.01.28
백준 2565  (0) 2021.01.28
반응형

www.acmicpc.net/problem/1748

 

1748번: 수 이어 쓰기 1

첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int n, i, ans;
int pow(int x, int n) {
    if (n == 0)
        return 1;
    return x * pow(x, n - 1);
}
int main() {
    cin >> n;
    i = 1;
    while (n >= pow(10, i)) {
        ans += 9 * pow(10, i - 1) * i;
        i++;
    }
    ans += (n - pow(10, i - 1) + 1) * i;
    cout << ans;
}
cs
반응형

+ Recent posts

티스토리툴바