https://www.acmicpc.net/problem/4781

 

4781번: 사탕 가게

각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개

www.acmicpc.net

 

배낭문제로 해결할 수 있는 문제입니다.

 

가격 정보가 소수점 둘째자리까지 주어지므로 정수로 바꿔서 계산하였습니다.

다만 문제점은 반올림을 하기 위해 * 100 + 0.5를 해줘야한다는 점입니다.

 

 

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>
#include <cstring>
using namespace std;
typedef long long ll;
 
pair<int, int> list[5001];
ll dp[10001];
int N, M;
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= M; j++) {
            if (list[i].second > j) continue;
 
            dp[j] = max(dp[j], dp[j - list[i].second] + list[i].first);
        }
    }
 
    cout << dp[M] << '\n';
}
 
void input() {
    double d;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> d;
        list[i].second = d * 100 + 0.5;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    double d;
    while (1) {
        cin >> N >> d;
        M = d * 100 + 0.5;
        if (!N) return 0;
 
        input();
        func();
        memset(dp, 0, sizeof(dp));
    }
}
 cs

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

boj 1311 할 일 정하기 1  (0) 2021.06.21
boj 1577 도로의 개수  (0) 2021.06.20
boj 2186 문자판  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18
boj 1563 개근상  (0) 2021.06.02

https://www.acmicpc.net/problem/2186

 

2186번: 문자판

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의

www.acmicpc.net

영어 단어가 "BREAK"처럼 주어지면 문자 판에서 "BREAK"라는 글자가 몇 번 나오는지 구하는 문제입니다.

일단 기본적으로 dfs를 통해 구해주시면 되고, 모든 위치에서 시작할 수 있으니 단어의 첫 알파벳과 일치하는 위치를 시작으로 dfs를 돌려줍니다.

 

하지만 이 문제는 이동 방법이 상하좌우로 K칸까지 이동할 수 있으므로 훨씬 많은 이동이 발생하므로 dp를 같이 사용해줍니다.

dp[x][y][idx] : (x, y)에 도달하였을 때 현재 찾고자 하는 단어의 인덱스가 idx인 경우의 수

이렇게 놓을 수 있습니다.

 

문제의 답은 int범위라고 명시되어 있기때문에 long long은 사용하지 않아도 됩니다.

 

dp를 사용하지 않으면 시간초과가 발생하므로 dp는 필수입니다!!

 

 

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
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
 
string str;
char list[110][110];
int dp[100][100][81];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, K, strLength;
 
int dfs(int x, int y, int idx) {
    if (idx == strLength) return 1;
 
    int &ret = dp[x][y][idx];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= K; j++) {
            int nx = x + direct[i][0] * j;
            int ny = y + direct[i][1] * j;
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (list[nx][ny] != str[idx]) continue;
 
            ret += dfs(nx, ny, idx + 1);
        }
    }
 
    return ret;
}
 
void func() {
    int ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (list[i][j] != str[0]) continue;
 
            ans += dfs(i, j, 1);
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
    cin >> str;
    strLength = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 1577 도로의 개수  (0) 2021.06.20
boj 4781 사탕 가게  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18
boj 1563 개근상  (0) 2021.06.02
boj 10800 컬러볼  (0) 2021.04.09

https://www.acmicpc.net/problem/13325

 

13325번: 이진 트리

입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가

www.acmicpc.net

루트에서 모든 리프노드 까지의 거리가 모두 같게만든 후 모든 가중치의 합의 최소를 구하는 문제입니다.

 

입력으로 주어지는 트리는 무조건 포화 이진 트리(perfect binary tree)이고,

이 문제는 독특하게 노드가 아닌 간선만 입력으로 주어집니다.

 

높이가 1이면 2개의 가중치, 2면 4개의 가중치이므로 높이 N에는 2^N개의 가중치가 있다는 것을 알 수 있습니다.

따라서 입력으로 2가 주어지면 높이가 1인 가중치(2) + 2인 가중치(4) = 총 6개를 입력으로 받습니다.

 

이 문제는 리프에서부터 같은 부모로 이어지는 간선 두개를 비교하여 합을 같게 맞추는 식으로 루트까지 올라가면서 계산하는 방식으로 해결할 수 있습니다.

 

 

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
#include <iostream>
#include <algorithm>
using namespace std;
 
int list[1 << 21];
int N, ans;
 
void func() {
    for (int i = N; i > 0; i--) {
        for (int j = (1 << i); j < (1 << (i + 1)); j += 2) {
            ans += abs(list[j] - list[j + 1]);
 
            list[j / 2] += max(list[j], list[j + 1]);
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 2; i < (1 << N + 1); i++) {
        cin >> list[i];
        ans += list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs
 
 
  

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

boj 4781 사탕 가게  (0) 2021.06.19
boj 2186 문자판  (0) 2021.06.19
boj 1563 개근상  (0) 2021.06.02
boj 10800 컬러볼  (0) 2021.04.09
boj 12869 뮤탈리스크  (0) 2021.04.04

https://www.acmicpc.net/problem/6059

 

6059번: Pasture Walking

The N cows (2 <= N <= 1,000) conveniently numbered 1..N are grazing among the N pastures also conveniently numbered 1..N. Most conveniently of all, cow i is grazing in pasture i. Some pairs of pastures are connected by one of N-1 bidirectional walkways tha

www.acmicpc.net

문제는 영어로 되어있지만 lca 알고리즘을 응용해볼 수 있는 문제입니다.

요약하자면 구성된 트리에서 임의의 2개의 노드 간의 거리를 출력하는 문제입니다.

 

parent를 구할때 그 parent까지 가는 거리도 같이 구해줍니다.

 

이 풀이로 풀 수 있는 문제로는 icpc.me/1761 (정점들의 거리)가 있습니다.

 

 

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
#include <iostream>
#include <vector>
#define MAX 1000
#define LOG 11
using namespace std;
 
vector<pair<int, int> > graph[MAX + 1];
pair<int, int> parent[MAX + 1][LOG];
int depth[MAX + 1];
int N, M;
 
void dfs(int v, int d) {
    depth[v] = d;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i].first;
        int w = graph[v][i].second;
 
        if (depth[next]) continue;
        parent[next][0] = { v, w };
        dfs(next, d + 1);
    }
}
 
int lca(int u, int v) {
    int ans = 0;
    if (depth[u] > depth[v]) swap(u, v);
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[v] - depth[u] >= (1 << i)) {
            ans += parent[v][i].second;
            v = parent[v][i].first;
        }
    }
    if (u == v) return ans;
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (parent[u][i].first != parent[v][i].first) {
            ans += (parent[u][i].second + parent[v][i].second);
            u = parent[u][i].first;
            v = parent[v][i].first;
        }
    }
 
    return ans + (parent[u][0].second + parent[v][0].second);
}
 
void func() {
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= N; i++) {
            parent[i][j].first = parent[parent[i][j - 1].first][j - 1].first;
            if (!parent[i][j].first) continue;
            parent[i][j].second = parent[i][j - 1].second + parent[parent[i][j - 1].first][j - 1].second;
        }
    }
 
    int u, v;
    while (M--) {
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
}
 
void input() {
    int u, v, w;
    cin >> N >> M;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v >> w;
        graph[u].push_back({ v,w });
        graph[v].push_back({ u,w });
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    dfs(1, 1);
    func();
 
    return 0;
}
 cs

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

boj 3584 가장 가까운 공통 조상  (0) 2021.06.16
boj 1626 두 번째로 작은 스패닝 트리  (0) 2021.04.02
boj 15481 그래프와 MST  (0) 2021.04.01
boj 15480 LCA와 쿼리  (0) 2021.02.14
boj 11438 LCA 2  (0) 2021.02.11

https://www.acmicpc.net/problem/3584

 

3584번: 가장 가까운 공통 조상

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두

www.acmicpc.net

LCA 알고리즘을 연습해볼 수 있는 간단한 문제입니다.

다만 이 문제는 방향 그래프이고, 루트가 정해져 있습니다.

 

저는 루트 확인을 chk 배열로 확인하였고, 입력이 자식으로 들어오지 않은 노드를 루트로 지정해주었습니다.

그리고 구했던 root를 시작으로 dfs를 돌려 각 노드의 depth를 구해주면서 자신들의 부모노드를 저장해줍니다. (parent[next][0] = v)

 

이제 자신의 2^n번째 조상을 모두 구하여 lca알고리즘으로 가장 가까운 공통 조상을 출력해줍니다.

 

이 문제는 입력이 10000개이므로 lca를 사용하지 않아도 풀리는 문제입니다.

자신의 부모만 구하여 최소 공통 조상을 구하는 방법인데 u, v의 높이를 같게 맞춘 다음 부모가 같아질때까지 한칸씩 위로 올리는 방식입니다.

소스 같이 올리겠습니다.

 

이 문제는 입력 범위가 작아서 그런지 시간은 동일하게 나왔습니다.

 

 

[LCA 사용]

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
#include <iostream>
#include <vector>
#include <cstring>
#define MAX 10000
#define LOG 15
using namespace std;
 
vector<int> graph[MAX + 1];
bool chk[MAX + 1];
int depth[MAX + 1];
int parent[MAX + 1][LOG];
int N, s, e, root;
 
void dfs(int v, int d) {
    depth[v] = d;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i];
        
        if (depth[next]) continue;
        parent[next][0] = v;
        dfs(next, d + 1);
    }
}
 
int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[v] - depth[u] >= (1 << i)) {
            v = parent[v][i];
        }
    }
    if (u == v) return u;
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
 
    return parent[v][0];
}
 
void func() {
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= N; i++) {
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
        }
    }
 
    cout << lca(s, e) << '\n';
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        chk[v] = true;
    }
 
    for (int i = 1; i <= N; i++) {
        if (!chk[i]) {
            root = i;
            break;
        }
    }
 
    cin >> s >> e;
}
 
void init() {
    memset(depth, 0, sizeof(depth));
    memset(parent, 0, sizeof(parent));
    memset(chk, false, sizeof(chk));
    for (int i = 1; i <= N; i++) graph[i].clear();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        dfs(root, 1);
        func();
        init();
    }
 
    return 0;
}
 cs

 

 

[LCA 사용X]

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
#include <iostream>
#include <vector>
#include <cstring>
#define MAX 10000
using namespace std;
 
vector<int> graph[MAX + 1];
bool chk[MAX + 1];
int depth[MAX + 1];
int parent[MAX + 1];
int N, s, e, root;
 
void dfs(int v, int d) {
    depth[v] = d;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i];
        
        if (depth[next]) continue;
        parent[next] = v;
        dfs(next, d + 1);
    }
}
 
int func(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
 
    while (depth[u] != depth[v]) {
        v = parent[v];
    }
 
    if (u == v) return u;
 
    while (parent[u] != parent[v]) {
        u = parent[u];
        v = parent[v];
    }
 
    return parent[u];
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        chk[v] = true;
    }
 
    for (int i = 1; i <= N; i++) {
        if (!chk[i]) {
            root = i;
            break;
        }
    }
 
    cin >> s >> e;
}
 
void init() {
    memset(depth, 0, sizeof(depth));
    memset(parent, 0, sizeof(parent));
    memset(chk, false, sizeof(chk));
    for (int i = 1; i <= N; i++) graph[i].clear();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        dfs(root, 1);
        cout << func(s, e) << '\n';
        init();
    }
 
    return 0;
}
 cs

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

boj 6059 Pasture Walking  (0) 2021.06.16
boj 1626 두 번째로 작은 스패닝 트리  (0) 2021.04.02
boj 15481 그래프와 MST  (0) 2021.04.01
boj 15480 LCA와 쿼리  (0) 2021.02.14
boj 11438 LCA 2  (0) 2021.02.11

https://www.acmicpc.net/problem/1563

 

1563번: 개근상

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독

www.acmicpc.net

점화식 구하는게 좀 복잡할 수도 있는 dp문제입니다.

문제를 풀고나서 다른분들의 풀이를 보니 3차원배열을 사용하셨던데 저는 2차원 dp배열로 해결하였습니다.

 

우선 이 문제는 지각을 두 번 이상 하거나, 결석을 세 번 연속으로 하는 경우를 제외한 모든 경우의 수를 구해야합니다.

 

손으로 직접 그려본 후에 점화식을 찾았습니다.

dp[N][start] : 학기 첫날(start)이 출석 / 지각 / 결석일 때 N번째 날의 경우의 수

		[0]	[1]	[2]	sum
N = 1	 1	1	1	3

N = 2	 3	2	3	8

N = 3	 8	4	7	19

N = 4	 19	7	17	43

N = 5	 43	13	38	94

N = 6	 94	24	82	200

 

dp[N][0] : 첫날이 출석인 경우의 수

 -> dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]

dp[N][1] : 첫날이 지각인 경우의 수

 -> dp[N - 1][1] + dp[N - 2][1] + dp[N - 3][1]

dp[N][2] : 첫날이 결석인 경우의 수

 -> dp[N - 1][0] + dp[N - 1][1] + dp[N - 2][0] + dp[N - 2][1]

 

출력은 dp[N][0 ~ 2]를 더해 1000000으로 mod연산한 값을 출력해주시면 됩니다.

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
#include <iostream>
#define MOD 1000000
using namespace std;
 
int dp[1001][3];
int N;
 
void init() {
    dp[0][1] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][2] = 1;
    dp[2][0] = 3;
    dp[2][1] = 2;
    dp[2][2] = 3;
    for (int i = 3; i <= 1000; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
        dp[i][1] = (dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][1]) % MOD;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 2][0] + dp[i - 2][1]) % MOD;
    }
}
 
void input() {
    cin >> N;
    cout << (dp[N][0] + dp[N][1] + dp[N][2]) % MOD << '\n';
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    input();
 
    return 0;
}
 cs

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

boj 2186 문자판  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18
boj 10800 컬러볼  (0) 2021.04.09
boj 12869 뮤탈리스크  (0) 2021.04.04
boj 1520 내리막 길  (0) 2021.03.28

www.acmicpc.net/problem/17143

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.

www.acmicpc.net

낚시왕은 1번 열부터 N번 열까지 1초에 한칸씩 움직이며 차례대로 낚시를 합니다.

1초동안 일어나는 일은

1. 낚시왕이 오른쪽으로 한 칸 이동합니다.

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡습니다.

3. 상어가 이동합니다.

 

상어에 대한 정보는 좌표(x, y), 속력(s), 이동 방향(d), 크기(z)가 주어지며, 이동 방향에 맞춰서 속력만큼 이동합니다.

이동 중에 맵 밖으로 나가려고 하는 경우에는 방향을 반대로 바꿔준 후에 그대로 이동합니다.

 

상어가 이동을 마쳤을 때 같은 칸에 여러마리의 상어가 있을 수 있는데 이 경우에는 크기가 가장 큰 상어만 살아남습니다.

 

이 조건들을 모두 고려하여 시뮬레이션을 돌렸을 때 낚시왕이 잡은 상어의 크기 합을 구하는 문제입니다.

 

 

저는 두가지 방법으로 해결해보았습니다.

1. 배열의 모든 칸을 클래스화해서 관리하는 방법

2. 배열에는 상어의 번호만 유지하는 방법

 

먼저 첫 번째 방법입니다.

저는 모든 칸을 클래스화해서 관리하였습니다. (속력, 방향, 크기)

상어가 없는 칸은 (0, 0, 0)이 채워져있을 것이고, 상어가 있는 칸은 (speed, d, size)가 채워져 있습니다.

 

먼저 낚시왕이 상어를 잡고, 상어를 이동시켜줍니다.

이동을 완료한 상어들이 같은 좌표에 있으면 제거를 해야하기 때문에 상어들의 새로운 위치를 구별해주기 위한 새로운 배열(tmp)을 사용하였습니다.

 

우선 속력만큼 이동을 모두 시켜준다면 시간초과가 뜰것 같아서 mod를 사용하였습니다.

상어가 가로로 이동 중이라면 %((M - 1) * 2), 세로로 이동 중이라면 %((N - 1) * 2)만큼만 이동하였습니다.

 

tmp[nx][ny].size가 0이면 상어가 없으므로 상어를 넣어줍니다.

tmp[nx][ny].size가 0이 아니면 이미 다른 상어가 도착한 상태이므로 크기가 큰 상어로 갱신합니다.

 

이 과정을 낚시왕이 맵밖으로 나갈때까지 반복한 후에 크기 합을 출력해줍니다.

 

 

 

 

두 번째 방법입니다.

shark라는 클래스 배열을 이용하여 상어들의 정보를 담아놓습니다. (번호, 좌표(x, y), 속력, 방향, 크기, 죽었는지 여부)

그리고 list배열에는 각 칸에 들어있는 상어의 번호를 저장합니다. (상어가 없으면 0)

 

로직은 첫 번째 방법과 같지만 다른 점은

1번 방법은 N * M을 돌면서 상어가 있는 칸에만 이동을 시키고, 상어의 모든 정보를 이동시켜야하므로 새로운 클래스배열을 선언하였지만

2번 방법은 상어의 수만큼만 반복하면 되고, 인덱스만 이동시키면 되기때문에 새로운 int배열을 선언하였다는 차이입니다.

 

1번 방법
2번 방법
2번 방법에서 mod를 사용하지 않음

시간은 비슷하지만 1번 방법의 메모리가 2번에 비해 엄청 많이 차지하였습니다.

그리고 상어를 움직일 때 mod를 사용하지 않고 돌려보니 시간 차이가 많이 나는것을 알 수 있습니다.

 

 

[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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int speed;
        int d;
        int size;
 
        public Pair(int speed, int d, int size) {
            this.speed = speed;
            this.d = d;
            this.size = size;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Pair> shark = new ArrayList<>();
    static Pair list[][] = new Pair[101][101];
    static int direct[][] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
    static int N, M, sharkCnt, ans;
 
    static Pair[][] moveShark() {
        Pair tmp[][] = new Pair[101][101];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                tmp[i][j] = new Pair(0, 0, 0);
            }
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j].size > 0) {
                    int dis = list[i][j].speed;
                    int d = list[i][j].d;
                    int size = list[i][j].size;
 
                    if (d > 1)
                        dis %= ((M - 1) * 2);
                    else
                        dis %= ((N - 1) * 2);
 
                    int nx = i;
                    int ny = j;
                    for (int k = 0; k < dis; k++) {
                        if (nx == 1 && d == 0)
                            d = 1;
                        else if (nx == N && d == 1)
                            d = 0;
                        else if (ny == 1 && d == 3)
                            d = 2;
                        else if (ny == M && d == 2)
                            d = 3;
 
                        nx += direct[d][0];
                        ny += direct[d][1];
                    }
 
                    if (tmp[nx][ny].size == 0) {
                        tmp[nx][ny].speed = list[i][j].speed;
                        tmp[nx][ny].d = d;
                        tmp[nx][ny].size = size;
                    } else {
                        if (tmp[nx][ny].size < size) {
                            tmp[nx][ny].speed = list[i][j].speed;
                            tmp[nx][ny].d = d;
                            tmp[nx][ny].size = size;
                        }
                    }
                }
            }
        }
 
        return tmp;
    }
 
    static void func() {
        for (int j = 1; j <= M; j++) {
            for (int i = 1; i <= N; i++) {
                if (list[i][j].size > 0) {
                    ans += list[i][j].size;
                    list[i][j].speed = 0;
                    list[i][j].d = 0;
                    list[i][j].size = 0;
                    break;
                }
            }
            if (j == M)
                break;
 
            list = moveShark();
        }
 
        System.out.println(ans);
    }
 
    static void init() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++)
                list[i][j] = new Pair(0, 0, 0);
        }
    }
 
    static void input() throws Exception {
        int x, y, s, d, z;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sharkCnt = Integer.parseInt(st.nextToken());
        init();
        for (int i = 0; i < sharkCnt; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            z = Integer.parseInt(st.nextToken());
 
            list[x][y].speed = s;
            list[x][y].d = d - 1;
            list[x][y].size = z;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

 

 

[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
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int idx;
        int x;
        int y;
        int speed;
        int d;
        int size;
        boolean die;
 
        public Pair(int idx, int x, int y, int speed, int d, int size) {
            this.idx = idx;
            this.x = x;
            this.y = y;
            this.speed = speed;
            this.d = d;
            this.size = size;
            this.die = false;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int newlist[][] = new int[101][101];
    static int list[][] = new int[101][101];
    static Pair shark[] = new Pair[10001];
    static int direct[][] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
    static int N, M, sharkCnt, ans;
 
    static void moveShark() {
        for (int i = 1; i <= N; i++)
            Arrays.fill(newlist[i], 0);
 
        for (int i = 1; i <= sharkCnt; i++) {
            int x = shark[i].x;
            int y = shark[i].y;
            int speed = shark[i].speed;
            int d = shark[i].d;
            int size = shark[i].size;
            boolean die = shark[i].die;
 
            if (die)
                continue;
 
            if (d > 1)
                speed %= ((M - 1) * 2);
            else
                speed %= ((N - 1) * 2);
 
            int nx = x;
            int ny = y;
            for (int k = 0; k < speed; k++) {
                if (nx == 1 && d == 0)
                    d = 1;
                else if (nx == N && d == 1)
                    d = 0;
                else if (ny == 1 && d == 3)
                    d = 2;
                else if (ny == M && d == 2)
                    d = 3;
 
                nx += direct[d][0];
                ny += direct[d][1];
            }
            shark[i].d = d;
 
            if (newlist[nx][ny] == 0) {
                newlist[nx][ny] = i;
                shark[i].x = nx;
                shark[i].y = ny;
            } else {
                int idx = newlist[nx][ny];
                int presize = shark[idx].size;
                if (presize < size) {
                    shark[idx].die = true;
                    newlist[nx][ny] = i;
                    shark[i].x = nx;
                    shark[i].y = ny;
                } else {
                    shark[i].die = true;
                }
            }
        }
    }
 
    static void func() {
        for (int j = 1; j <= M; j++) {
            for (int i = 1; i <= N; i++) {
                if (list[i][j] > 0) {
                    int idx = list[i][j];
                    ans += shark[idx].size;
                    shark[idx].die = true;
                    list[i][j] = 0;
                    break;
                }
            }
            if (j == M)
                break;
 
            moveShark();
            for (int x = 1; x <= N; x++)
                for (int y = 1; y <= M; y++)
                    list[x][y] = newlist[x][y];
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int x, y, s, d, z;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sharkCnt = Integer.parseInt(st.nextToken());
 
        for (int i = 1; i <= sharkCnt; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            z = Integer.parseInt(st.nextToken());
 
            shark[i] = new Pair(i, x, y, s, d - 1, z);
            list[x][y] = i;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 1756 피자 굽기  (0) 2024.08.08
boj 3758 KCPC  (0) 2024.06.09
boj 20207 달력  (0) 2021.04.22
boj 17144 미세먼지 안녕!  (0) 2021.04.14
boj 2564 경비원  (0) 2021.04.13

www.acmicpc.net/problem/20207

 

20207번: 달력

 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다.  여름이 거의 끝나가자 장

www.acmicpc.net

시간정보를 입력받으면서 l ~ r시간의 등장횟수를 1씩 증가시킵니다.

 

이제 연속된 구간에서의 최댓값을 갱신하면서, list[i] = 0이 되는 시점에서 지금까지 연속으로 등장했던 시간 * 최댓값을 계속 더해주시면 됩니다.

이후에는 다음 구간을 구하기 위해 con과 max를 0으로 다시 초기화시켜줍니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[] = new int[366];
    static int N, ans;
 
    static void func() {
        int max = 0;
        int con = 0;
        for (int i = 1; i <= 365; i++) {
            if (list[i] > 0) {
                con++;
                max = Math.max(max, list[i]);
            } else {
                ans += (con * max);
                con = 0;
                max = 0;
            }
        }
 
        ans += (con * max);
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int l, r;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            l = Integer.parseInt(st.nextToken());
            r = Integer.parseInt(st.nextToken());
 
            for (int j = l; j <= r; j++)
                list[j]++;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 3758 KCPC  (0) 2024.06.09
boj 17143 낚시왕  (0) 2021.04.23
boj 17144 미세먼지 안녕!  (0) 2021.04.14
boj 2564 경비원  (0) 2021.04.13
boj 16719 ZOAC  (0) 2021.03.15

www.acmicpc.net/problem/19236

 

19236번: 청소년 상어

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는

www.acmicpc.net

이 문제는 고려해야할 부분이 많습니다.

 

상어와 물고기는 8방향 이동을 할 수 있습니다.

순서는 (1)상어가 물고기를 먹고 (2)물고기들이 이동합니다.

상어가 처음에는 (0, 0)에 있는 물고기를 먹으며 먹은 물고기의 방향을 갖게되고, 이후에는 주어진 방향으로만 이동합니다.

 

상어는 한 번에 여러 칸을 이동할 수 있고, 물고기가 있는 칸으로만 이동할 수 있습니다.

따라서 이동경로에 있는 물고기 후보 중 하나를 골라 먹습니다.

 

물고기는 맵 밖이나 상어가 있는 칸으로 이동할 수 없으며 이동할 때 번호가 작은 물고기부터 순서대로 이동합니다. (1번 ~ 16번)

(만약, 해당 번호의 물고기가 먹힌상태면 다음 번호가 이동하면 됩니다.)

물고기는 주어진 방향으로만 1칸 이동하며, 그 칸에 물고기가 있으면 서로의 자리를 바꿉니다.

만약 물고기가 이동할 수 없는 경우에는 이동할 수 있을 때까지 방향을 45도 반시계 방향으로 회전한 후 이동합니다.

 

 

이제 제 로직을 설명하겠습니다.

 

저는 입력을 받으면서 (0, 0)에 상어를 미리 놓고, (1)물고기들 이동, (2)상어 이동 순서대로 구현하였습니다.

func함수의 파라미터에 (현재 배열의 상태(arr), 물고기의 상태(f), 상어의 좌표(X, Y), 상어의 방향(D), 현재 먹은 물고기들의 번호합(S))

을 넘겨주는 재귀함수로 구성하였습니다.

 

함수가 돌 때마다 최대 합을 갱신해주었고, 물고기 이동부터 시작합니다.

먹히지 않은 물고기들만 이동하는 방식이며, 물고기가 이동할 수 있을 때까지 방향을 45도씩 반시계방향으로 회전시키며 반복문을 돌렸습니다.

물고기가 이동하고나면 break를 합니다.

 

이제 상어가 이동합니다.

상어는 한 방향으로만 움직일 수 있지만 여러 칸 이동이 가능하므로 맵 밖으로 나갈 때까지 반복문을 돌려줍니다.

물고기가 없는 칸은 갈 수 없으므로 continue를 하였고, 물고기가 있는 칸은 먹은 후의 상태를 다음 재귀로 넘겨주었습니다. (이는 백트래킹으로 구현하였습니다.)

 

상어와 물고기의 모든 이동이 끝나면 계속 갱신해주었던 답을 출력해줍니다.

 

 

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
114
115
116
117
118
119
120
121
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int x, y, d;
 
        public Pair(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int direct[][] = { { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 } };
    static boolean eat[] = new boolean[17];
    static int ans;
 
    static void func(int[][] arr, Pair[] f, int X, int Y, int D, int S) {
        ans = Math.max(ans, S);
        for (int i = 1; i <= 16; i++) {
            if (eat[i])
                continue;
 
            int x = f[i].x;
            int y = f[i].y;
 
            int nx = x;
            int ny = y;
 
            while (true) {
                nx = x + direct[f[i].d][0];
                ny = y + direct[f[i].d][1];
 
                if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) {
                    f[i].d = (f[i].d + 1) % 8;
                    continue;
                }
                if (arr[nx][ny] == -1) {
                    f[i].d = (f[i].d + 1) % 8;
                    continue;
                }
 
                if (arr[nx][ny] == 0) {
                    f[i].x = nx;
                    f[i].y = ny;
                    arr[nx][ny] = arr[x][y];
                    arr[x][y] = 0;
                } else {
                    int tmp = arr[x][y];
                    f[arr[nx][ny]].x = x;
                    f[arr[nx][ny]].y = y;
                    f[i].x = nx;
                    f[i].y = ny;
                    arr[x][y] = arr[nx][ny];
                    arr[nx][ny] = tmp;
                }
                break;
            }
        }
 
        int nx = X;
        int ny = Y;
        while (true) {
            nx = nx + direct[D][0];
            ny = ny + direct[D][1];
 
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4)
                break;
            if (arr[nx][ny] == 0)
                continue;
 
            int tmp = arr[nx][ny];
            arr[nx][ny] = -1;
            arr[X][Y] = 0;
            eat[tmp] = true;
            int arr2[][] = new int[4][4];
            for (int i = 0; i < 4; i++)
                arr2[i] = arr[i].clone();
            Pair f2[] = new Pair[17];
            for (int i = 1; i <= 16; i++)
                f2[i] = new Pair(f[i].x, f[i].y, f[i].d);
            func(arr2, f2, nx, ny, f[tmp].d, S + tmp);
            eat[tmp] = false;
            arr[nx][ny] = tmp;
            arr[X][Y] = -1;
        }
    }
 
    public static void main(String[] args) throws Exception {
        int list[][] = new int[4][4];
        Pair fish[] = new Pair[17];
 
        int nowx = 0, nowy = 0, nowd = 0, sum = 0;
        int x, d;
        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
 
                x = Integer.parseInt(st.nextToken());
                d = Integer.parseInt(st.nextToken()) - 1;
 
                list[i][j] = x;
                fish[x] = new Pair(i, j, d);
                if (i == 0 && j == 0) {
                    list[i][j] = -1;
                    eat[x] = true;
                    nowx = i;
                    nowy = j;
                    nowd = d;
                    sum += x;
                }
            }
        }
        func(list, fish, nowx, nowy, nowd, sum);
        System.out.println(ans);
    }
}
 cs

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

boj 30893 트리 게임  (0) 2024.07.19
boj 19542 전단지 돌리기  (0) 2024.06.19
boj 2239 스도쿠  (0) 2021.04.16
boj 2458 키 순서  (0) 2021.04.13
boj 14889 스타트와 링크  (0) 2021.03.17

www.acmicpc.net/problem/1194

 

1194번: 달이 차오른다, 가자.

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,

www.acmicpc.net

기본적인 bfs에 비트마스킹이 더해진 문제입니다.

 

visit[x][y][key] : (x, y)에 도달했을 때 갖고있는 열쇠 종류

문을 열기 위해서는 열쇠를 갖고있어야 하므로 얻은 열쇠를 비트마스킹을 이용하여 관리합니다.

 

로직은 다른 bfs와 똑같이 돌아가며, 확인해야할 조건은

1. 맵 밖으로 나갈 경우

2. 문을 만났을 경우

3. 열쇠를 만났을 경우

4. 해당 좌표를 이미 방문한 경우

5. 벽을 만난 경우

 

1, 4, 5인 경우에는 continue를 해주시면 되고,

2인 경우에는 열쇠가 없는 경우에만 continue를 해주시면 됩니다.

3인 경우에는 열쇠를 추가합니다.

 

탈출에 성공하였으면 현재 시간을 출력해주시고, 큐가 비었는데도 탈출하지 못했으면 -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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Deque<int[]> dq = new ArrayDeque<>();
    static char list[][] = new char[51][51];
    static boolean visit[][][] = new boolean[51][51][64];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M;
 
    static void bfs() {
        for (int t = 0; !dq.isEmpty(); t++) {
            int size = dq.size();
            while (size-- > 0) {
                int x = dq.peek()[0];
                int y = dq.peek()[1];
                int key = dq.poll()[2];
 
                if (list[x][y] == '1') {
                    System.out.println(t);
                    return;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = x + direct[i][0];
                    int ny = y + direct[i][1];
                    int nextKey = key;
 
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                        continue;
                    if ('A' <= list[nx][ny] && list[nx][ny] <= 'F') {
                        int door = list[nx][ny] - 'A';
 
                        if ((key & (1 << door)) == 0)
                            continue;
                    }
                    if ('a' <= list[nx][ny] && list[nx][ny] <= 'f') {
                        nextKey = nextKey | (1 << (list[nx][ny] - 'a'));
                    }
 
                    if (visit[nx][ny][nextKey] || list[nx][ny] == '#')
                        continue;
                    dq.add(new int[] { nx, ny, nextKey });
                    visit[nx][ny][nextKey] = true;
                }
            }
        }
        
        System.out.println(-1);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            for (int j = 0; j < M; j++) {
                if (list[i][j] == '0') {
                    dq.add(new int[] { i, j, 0 });
                    visit[i][j][0] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}
 cs

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

boj 16932 모양 만들기  (0) 2022.05.14
boj 17244 아맞다우산  (0) 2021.11.25
boj 17471 게리맨더링  (0) 2021.04.16
boj 2573 빙산  (0) 2021.04.05
boj 14923 미로 탈출  (0) 2021.03.29

www.acmicpc.net/problem/2273

 

2273번: 줄 서기

첫째 줄에 N(1≤N≤256), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

www.acmicpc.net

키를 비교한 두 학생의 번호 u, v가 주어집니다.

d[u][v] : u가 v보다 앞에서야하는 경우

이는 방향그래프이며 인접행렬을 만들어주고 플로이드로 상대적인 키 정보를 구합니다.

 

그리고 이중for를 돌리면서 d[i][j] = true이고, d[j][i] = true인 것을 찾아줍니다.

d[i][j]=true이면 i가 j보다 앞에 있어야한다는 뜻인데

d[j][i]=true이면 j가 i보다 앞에 있어야한다는 뜻이므로 둘다 true면 모순입니다. 이때는 -1을 출력하고 리턴합니다.

 

확인이 끝났으면 왼쪽 경계 값(l = 1), 오른쪽 경계 값(r = N)으로 두고 1번학생부터 확인합니다.

d[i][j]=true이면 i보다 뒤에 있어야하는 학생이 1명 추가됩니다. => r--;

d[j][i]=true이면 i보다 앞에 있어야하는 학생이 1명 추가됩니다. => l++;

 

모든 학생을 확인하고 l r 을 출력합니다.

 

 

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
#include <iostream>
using namespace std;
 
bool d[257][257];
int N, M;
 
void func() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (d[i][k] && d[k][j]) d[i][j] = true;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (d[i][j] && d[j][i]) {
                cout << "-1\n";
                return;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        int l = 1;
        int r = N;
        for (int j = 1; j <= N; j++) {
            if (d[i][j]) r--;
            else if (d[j][i]) l++;
        }
 
        cout << l << ' ' << r << '\n';
    }
}
 
void input() {
    int u, v;
    cin >> N >> M;
    while (M--) {
        cin >> u >> v;
        d[u][v] = true;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 14938 서강그라운드  (0) 2021.03.24

www.acmicpc.net/problem/17471

 

17471번: 게리맨더링

선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

www.acmicpc.net

선거구를 두 구간으로 나누는데 나눠진 구간끼리 연결되어 있어야합니다.

 

dfs기반의 부분집합으로 나눌 수 있는 모든 구간을 확인합니다.

두 구간을 div1, div2라는 리스트를 사용하였고, 구역들끼리 연결되어있는지 bfs를 통해 확인합니다.

구간의 모든 구역끼리 연결되어 있으면 구역들의 합의 최솟값을 갱신합니다.

두 선거구로 나눌 수 없는 경우가 입력으로 주어질 수 있으니 그 때는 -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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static ArrayList<Integer> graph[] = new ArrayList[11];
    static ArrayList<Integer> div1 = new ArrayList<>();
    static ArrayList<Integer> div2 = new ArrayList<>();
    static int list[] = new int[11];
    static boolean pick[] = new boolean[11];
    static boolean visit[] = new boolean[11];
    static int N, ans = 2147483647;
 
    static boolean bfs(ArrayList<Integer> div, int size, boolean t) {
        Arrays.fill(visit, false);
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(div.get(0));
        visit[div.get(0)] = true;
        int cnt = 0;
        while (!dq.isEmpty()) {
            int x = dq.poll();
            cnt++;
            for (int i = 0; i < graph[x].size(); i++) {
                int next = graph[x].get(i);
 
                if (visit[next] || pick[next] != t)
                    continue;
 
                visit[next] = true;
                dq.add(next);
            }
        }
 
        if (cnt == size)
            return true;
        else
            return false;
    }
 
    static void func(int idx) {
        if (!div1.isEmpty()) {
            for (int i = 1; i <= N; i++) {
                if (!pick[i])
                    div2.add(i);
            }
            
            if(!div2.isEmpty()) {
                if (bfs(div1, div1.size(), true)) {
                    if (bfs(div2, div2.size(), false)) {
                        int sum = 0;
                        for (int i = 0; i < div1.size(); i++) {
                            sum += list[div1.get(i)];
                        }
 
                        for (int i = 0; i < div2.size(); i++) {
                            sum -= list[div2.get(i)];
                        }
 
                        ans = Math.min(ans, Math.abs(sum));
                    }
                }
                div2.clear();
            }
        }
 
        for (int i = idx; i <= N; i++) {
            div1.add(i);
            pick[i] = true;
            func(i + 1);
            pick[i] = false;
            div1.remove(div1.size() - 1);
        }
    }
 
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
 
        int K, v;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            graph[i] = new ArrayList<>();
            while (K-- > 0) {
                v = Integer.parseInt(st.nextToken());
                graph[i].add(v);
            }
        }
    }
 
    static void print() {
        if (ans == 2147483647)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(1);
        print();
    }
}
 cs

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

boj 17244 아맞다우산  (0) 2021.11.25
boj 1194 달이 차오른다, 가자.  (0) 2021.04.21
boj 2573 빙산  (0) 2021.04.05
boj 14923 미로 탈출  (0) 2021.03.29
boj 17836 공주님을 구해라!  (0) 2021.03.26

+ Recent posts

티스토리툴바