BOJ : https://www.acmicpc.net/problem/6603

 

6603번: 로또

문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2

www.acmicpc.net

이 문제를 해결하는데 필요한 알고리즘 : BFS, Brute force, DFS, back tracking

 

백트래킹의 간단한 입문 문제이다.

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 <cstdio>
#include <vector>
using namespace std;
 
int N;
int arr[13];
vector<int> v;
 
void dfs(int start) {
    if (v.size() == 6) {
        for (int i = 0; i < 6; i++) {
            printf("%d ", v[i]);
        }
        printf("\n");
        return;
    }
 
    for (int i = start; i < N; i++) {
        if (v.size() < 6) {
            v.push_back(arr[i]);
            dfs(i + 1);
            v.pop_back();
        }
    }
}
 
int main() {
    while (1) {
        scanf("%d", &N);
        if (N == 0) break;
        for (int i = 0; i < N; i++) {
            scanf("%d", &arr[i]);
        }
        dfs(0);
        printf("\n");
    }
 
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2565번 전깃줄  (0) 2019.04.08
BOJ 14501번 퇴사  (0) 2019.04.07
1182번 : 부분수열의 합 - junnnho  (0) 2019.04.07
14502번 : 연구소 - Junnnho  (0) 2019.04.07
16235번 : 나무제테크 - Junnnho  (0) 2019.04.07

BOJ : https://www.acmicpc.net/problem/1182

dfs를 통해 모든 수를 다 방문하면서 합이 같아지는 부분이 있는지 확인했다.

 

1개는 현재의 합에서 현재 방문한 수를 빼고 다음수를 확인하는 재귀,

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
#include <cstdio>
#include <vector>
using namespace std;
 
int N, S, check;
int arr[20];
 
void dfs(int start, int sum) {
    sum += arr[start];
 
    if (start >= N)
        return;
 
    if (sum == S) {
        check++;
    }
 
    dfs(start + 1, sum - arr[start]);
    dfs(start + 1, sum);
}
 
int main() {
    scanf("%d%d", &N, &S);
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    dfs(0,0);
    printf("%d", check);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 14501번 퇴사  (0) 2019.04.07
6603번 : 로또 - junnnho  (0) 2019.04.07
14502번 : 연구소 - Junnnho  (0) 2019.04.07
16235번 : 나무제테크 - Junnnho  (0) 2019.04.07
BOJ 1463번 1로 만들기  (0) 2019.04.07

BOJ : https://www.acmicpc.net/problem/14502

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.  일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.

www.acmicpc.net

이 문제를 해결하는데 필요한 알고리즘 : BFS or Brute force (or DFS)

나는 BFS로 풀었다.

처음에는 배열의 크기를 생각하지 못하고 시간초과 없이 어떻게 해결해야하나 했는데

8*8 크기라면 전범위를 다돌아도 괜찮을 것 같았다.

바이러스가 없는 0 부분에 1을 2칸 집어넣고 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
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int arr[8][8];
int ans[8][8];
int Arr[8][8];
int temp[4] = { -1,1,0,0 };
int temp2[4] = { 0,0,-1,1 };
typedef pair<int, int> pii;
vector<pii> v;
int MAX, first, second;
int N, M, virus;
bool visit;
bool check[8][8];
 
void dfs(int n, int m) { // n -> 세로 m -> 가로
 
    for (int i = 0; i < 4; i++) {
        if (n + temp[i] >= 0 && n + temp[i] < N && m + temp2[i] >= 0 && m + temp2[i] < M) {
            if (arr[n + temp[i]][m + temp2[i]] == 0) {
                arr[n + temp[i]][m + temp2[i]] = 2;
                dfs(n + temp[i], m + temp2[i]);
            }
        }
    }
 
}
 
void lab() {
 
    if (virus == 3) {
        int zero = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                ans[i][j] = arr[i][j];
        for (int i = 0; i < v.size(); i++) {
            dfs(v[i].first, v[i].second);
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) zero++;
                arr[i][j] = ans[i][j];
                ans[i][j] = Arr[i][j];
            }
        }
        MAX = max(MAX, zero);
        return;
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i == N-1 && j == M-1) 
                visit = true;
            if (arr[i][j] == 0) {
                if (!check[i][j]) {
                    if (virus == 1)
                        check[i][j] = true, first = i, second = j;
                    arr[i][j] = 1, virus++;
                    lab();
                    if (i != first || j != second)
                        arr[i][j] = 0, virus--;
                }
            }
            if (visit == true) {
                if (i == first && j == second) {
                    visit = false;
                    if (first != N - 1 || second != M - 1) {
                        arr[first][second] = 0, virus--;
                        if (second != M - 1) {
                            j = second;
                        }
                        else {
                            i = first;
                            j = -1;
                        }
                    }
                }
                else return;
            }
        }
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
            Arr[i][j] = arr[i][j];
            if (arr[i][j] == 2) v.push_back(make_pair(i, j));
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0) {
                arr[i][j] = 1, virus = 1, visit = false;
                lab();
                if (Arr[N - 1][M - 1] != 1)
                    if (arr[N - 1][M - 1] == 1) arr[N - 1][M - 1] = 0;
                arr[i][j] = 0;
            }
            for (int i = 0; i < N; i++)
                for (int j = 0; j < M; j++)
                    check[i][j] = false;
        }
    }
 
    cout << MAX;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

6603번 : 로또 - junnnho  (0) 2019.04.07
1182번 : 부분수열의 합 - junnnho  (0) 2019.04.07
16235번 : 나무제테크 - Junnnho  (0) 2019.04.07
BOJ 1463번 1로 만들기  (0) 2019.04.07
BOJ 1965번 상자넣기  (0) 2019.04.07

BOJ : https://www.acmicpc.net/problem/16235

 

16235번: 나무 재테크

부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든

www.acmicpc.net

이 문제를 해결하는데 필요한 알고리즘 : 구현, BFS

 

그냥 문제에 적힌 그대로 따라가면 되는 문제이다.

sort를 잘못된 위치에 적어주면 시간초과가 발생할수 있으니,

어린 나무를 확인해야하는 봄에만 sort를 시켜주면 된다.

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 <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
int N, M, K, a, b, c, temp;
int A[11][11]; // A배열은 양분을 저장할 배열
int Aarr[11][11]; // Aarr배열은 현재 양분이 저장되어 있는 배열
int x[] = { -1,-1,-1,0,0,1,1,1 };
int y[] = { -1,0,1,-1,1,-1,0,1 };
int Summer[11][11];
typedef struct _Tree {
    vector<int> tree;
};
 
_Tree Tree[11][11];
 
void spring() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (Tree[i][j].tree.size() != 0) {
                sort(Tree[i][j].tree.begin(), Tree[i][j].tree.end());
                for (int k = 0; k < Tree[i][j].tree.size(); k++) {
                    if (Aarr[i][j] >= Tree[i][j].tree[k]) {
                        Aarr[i][j] -= Tree[i][j].tree[k];
                        Tree[i][j].tree[k]++;
                    }
                    else {
                        Summer[i][j] += Tree[i][j].tree[k] / 2;
                        Tree[i][j].tree.erase(Tree[i][j].tree.begin() + k--);
                    }
                }
            }
        }
    }
}
 
void summer() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            Aarr[i][j] += Summer[i][j];
            Summer[i][j] = 0;
        }
    }
}
 
void autumn() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (Tree[i][j].tree.size() != 0) {
                for (int k = 0; k < Tree[i][j].tree.size(); k++) {
                    if (Tree[i][j].tree[k] % 5 == 0) {
                        for (int h = 0; h < 8; h++) {
                            if (i + x[h] > 0 && i + x[h] <= N && j + y[h] > 0 && j + y[h] <= N) {
                                Tree[i + x[h]][j + y[h]].tree.push_back(1);
                            }
                        }
                    }
                }
            }
        }
    }
}
 
void winter() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            Aarr[i][j] += A[i][j];
        }
    }
}
 
int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &A[i][j]);
            Aarr[i][j] = 5;
        }
    }
    for (int i = 0; i < M; i++) {
        scanf("%d%d%d", &a, &b, &c);
        Tree[a][b].tree.push_back(c);
    }
    while (K--) {
        spring(), summer(), autumn(), winter();
    }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            temp += Tree[i][j].tree.size();
 
    printf("%d", temp);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

1182번 : 부분수열의 합 - junnnho  (0) 2019.04.07
14502번 : 연구소 - Junnnho  (0) 2019.04.07
BOJ 1463번 1로 만들기  (0) 2019.04.07
BOJ 1965번 상자넣기  (0) 2019.04.07
BOJ 1937번 욕심쟁이 판다  (0) 2019.04.06

+ Recent posts

티스토리툴바