문제

 

풀이

주어진 배열에서 l ~ r의 범위를 골라서 오름차순으로 정렬하고 idx번째에 위치한 수를 구하는 문제입니다.

N = 10000, M = 500이므로 브루트포스를 사용하여 M * N * logN 시간으로 해결할 수 있습니다.

저는 l ~ r 범위의 수들을 벡터에 넣어줬고, 벡터를 오름차순으로 정렬하여 idx번째 수를 출력하는 방식으로 해결했습니다.

 

코드

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
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10001
using namespace std;
 
int list[MAX];
int N, M;
 
void func() {
    int l, r, idx;
    while (M--) {
        cin >> l >> r >> idx;
        vector<int> tmp;
        for (int i = l; i <= r; i++) {
            tmp.push_back(list[i]);
        }
        sort(tmp.begin(), tmp.end());
        cout << tmp[idx - 1] << '\n';
        tmp.clear();
    }
}
 
void input() {
    int x;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22
엘리스 코드 챌린지 Day 4 트리 위의 게임  (0) 2024.07.22
엘리스 코드 챌린지 Day 3 문자열 압축 해제  (4) 2024.07.22
엘리스 코드 챌린지 Day 1 목표량  (0) 2024.07.22

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

 

14456번: Hoof, Paper, Scissors (Bronze)

You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors". The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to three and then each s

www.acmicpc.net

입력으로 주어지는 숫자는 가위인지, 바위인지, 보인지 알 수 없습니다.

이 문제는 숫자 1, 2, 3을 가위, 바위, 보로 적절히 분배하여 첫 번째 소가 이길 수 있는 최대 게임 수를 출력합니다.

 

race를 지정할 수 있는 경우의 수는 3! = 6가지

게임 수는 최대 100게임

따라서 브루트포스로 해결할 수 있습니다.

nextPermutation으로 race의 모든 경우를 확인할 수 있고, 그 때마다 첫 번째 소가 얻을 수 있는 점수를 구합니다.

그리고 그것들의 최댓값을 구하여 출력합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private final static int MAX = 100;
    private final static int RACE_CNT = 3;
    private static int race[] = {1, 2, 3};
    private static int list[][] = new int[MAX][2];
    private static int N;
 
    private static void swap(int i, int j) {
        int tmp = race[i];
        race[i] = race[j];
        race[j] = tmp;
    }
 
    private static boolean nextPermutation() {
        int i = RACE_CNT - 1;
        while (i > 0 && race[i - 1] > race[i]) {
            i--;
        }
 
        if (i == 0) {
            return false;
        }
 
        int j = RACE_CNT - 1;
        while (race[i - 1] > race[j]) {
            j--;
        }
        swap(i - 1, j);
 
        int k = RACE_CNT - 1;
        while (i < k) {
            swap(i++, k--);
        }
 
        return true;
    }
 
    private static int getScore(int x, int y) {
        if (x == 1 && y == 2) {
            return 1;
        } else if (x == 2 && y == 3) {
            return 1;
        } else if (x == 3 && y == 1) {
            return 1;
        } else {
            return 0;
        }
    }
 
    private static void func() {
        int ans = 0;
        do {
            int ret = 0;
            for (int i = 0; i < N; i++) {
                ret += getScore(race[list[i][0] - 1], race[list[i][1] - 1]);
            }
 
            ans = Math.max(ans, ret);
        } while (nextPermutation());
 
        System.out.println(ans);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

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

boj 17281 ⚾  (0) 2021.02.16
boj 3040 백설 공주와 일곱 난쟁이  (0) 2021.02.15
boj 2961 도영이가 만든 맛있는 음식  (0) 2021.02.15
boj 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데  (0) 2021.01.29
boj 1018 체스판 다시 칠하기  (0) 2021.01.29

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

 

16985번: Maaaaaaaaaze

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을

www.acmicpc.net

오랜만에 포스팅입니다. (너무 게을러서..)

 

bfs에 브루트포스까지 섞여있는 풀이가 복잡한 문제입니다.

5x5 크기의 2차원 배열이 5개 있으니 3차원 배열이 됩니다.

(0, 0, 0)에서 출발하여 (4, 4, 4)에 도착하는 최소 이동 횟수를 요구합니다.

여기까지만 보면, 단순 bfs로도 해결이 가능합니다.

 

하지만 5x5 크기의 판들의 순서도 변경이 가능하고, 판을 회전할 수도 있습니다.

브루트포스를 이 제약조건 두 개에 각각 적용해야 합니다.

 

저는 이 판들의 인덱스로 번호를 매겼고, dfs로 순회하면서 이동 횟수의 최솟값을 구하고, 회전 로직을 구현했습니다.

1
2
3
4
do {
    copyArray();
    dfs(0);
} while (next_permutation(order, order + MAX));
 cs

먼저, 순열을 이용하여 판들의 순서를 바꿔줍니다.

cpp은 next_permutation을 제공하여 편하게 구현할 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int idx) {
    if (idx == MAX) return;
 
    for (int i = 0; i < 4; i++) {
        int ret = bfs();
 
        if (ret != -1) {
            ans = min(ans, ret);
        }
 
        dfs(idx + 1);
        rotate(idx);
    }
}
 cs

처음 제출했을 때의 dfs 함수입니다.

모든 경우에서 bfs로 이동 횟수를 구하고, 회전하는 방식입니다.

 

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
int bfs() {
    queue<pair<int, pair<int, int> > > q;
    q.push({ 0,{0,0} });
    memset(visit, false, sizeof(visit));
    visit[0][0][0] = true;
    for (int t = 0; !q.empty(); t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().first;
            int y = q.front().second.first;
            int z = q.front().second.second;
            q.pop();
 
            if (x == MAX - 1 && y == MAX - 1 && z == MAX - 1) {
                return t;
            }
 
            for (int d = 0; d < 6; d++) {
                int nx = x + direct[d][0];
                int ny = y + direct[d][1];
                int nz = z + direct[d][2];
 
                if (nx < 0 || ny < 0 || nz < 0 || nx >= MAX || ny >= MAX || nz >= MAX) continue;
                if (visit[nx][ny][nz] || !map[nx][ny][nz]) continue;
 
                q.push({ nx,{ny,nz} });
                visit[nx][ny][nz] = true;
            }
        }
    }
 
    return -1;
}
 cs

bfs로 이동 횟수를 구합니다.

중간에 도착 지점을 만났다면 t를 리턴, 아니면 -1을 리턴합니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void rotate(int idx) {
    int tmp[MAX][MAX][MAX] = { 0, };
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            tmp[idx][i][j] = map[idx][j][MAX - 1 - i];
        }
    }
 
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            map[idx][i][j] = tmp[idx][i][j];
        }
    }
}
 cs

현재 단계에서 이동횟수를 모두 구했다면 배열을 회전합니다.

회전은 90도, -90도 중에 아무렇게나 해주시면 됩니다. 한 방향으로 회전하는 것이 중요합니다.

이렇게 하시면 AC는 받을 수 있습니다.

하지만 다른 분들의 실행 시간을 보니 제 코드가 비효율적으로 동작한다는 것을 깨달았고, 가지치기를 진행하였습니다.

위의 코드들은 가지치기 이전 단계의 코드이며, 변화가 있는 로직은 rotate와 dfs입니다.

 

생각을 해보니, 문제에 답이 있었다는 것을 깨달았습니다.

  1. 참가자가 들어갈 수 없는 칸이 존재한다.
    • 그 칸이 시작/도착 지점이라면 bfs 탐색할 필요가 없다.
    • 배열은 회전하므로 시작/도착 지점이 갈 수 없는 칸일 가능성이 있다.
  2. 배열 크기는 5 x 5 x 5로 고정되어 있다.
    • 탈출이 가능한 배열에서 나올 수 있는 최소 이동 횟수는 12다.
  3. 회전을 해도 이전과 같은 모양이 나올 수 있다.
    • 이미 구한 것으로 간주하고, 다음 단계를 진행할 필요가 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool rotate(int idx) {
    int tmp[MAX][MAX][MAX] = { 0, };
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            tmp[idx][i][j] = map[idx][j][MAX - 1 - i];
        }
    }
 
    int cnt = 0;
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (map[idx][i][j] == tmp[idx][i][j]) cnt++;
            map[idx][i][j] = tmp[idx][i][j];
        }
    }
 
    if (cnt == MAX * MAX) return false;
    else return true;
}
 cs

우선 rotate입니다.

자료형은 bool로 변경되었고, 회전한 배열이 이전 배열과 같은지 확인하는 로직만 추가되었습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int idx) {
    if (idx == MAX) {
        if (!map[MAX - 1][MAX - 1][MAX - 1]) {
            return;
        }
 
        int ret = bfs();
        if (ret != -1) {
            ans = min(ans, ret);
        }
 
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        if (map[0][0][0]) {
            dfs(idx + 1);
            if (ans == MIN_ANS) return;
        }
 
        if (!rotate(idx)) return;
    }
}
 cs

dfs 함수에 많은 변화가 있었습니다.

bfs 함수 호출은 모든 회전이 한 번씩 끝났을 때 진행하는 것으로 변경하였고, 출발/도착 지점에 대한것과 최솟값, rotate에 대한 가지치기가 모두 포함되어 있습니다.

이제 제출을 해보니 시간이 많이 줄어든 것을 확인할 수 있습니다.

 

 

최종 코드는 아래입니다.

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
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAX 5
#define MIN_ANS 12
using namespace std;
 
int list[MAX][MAX][MAX], map[MAX][MAX][MAX];
int order[MAX], ans;
int direct[6][3] = { {0,0,1}, {0,0,-1}, {0,1,0}, {0,-1,0}, {1,0,0}, {-1,0,0} };
bool visit[MAX][MAX][MAX];
 
int bfs() {
    queue<pair<int, pair<int, int> > > q;
    q.push({ 0,{0,0} });
    memset(visit, false, sizeof(visit));
    visit[0][0][0] = true;
    for (int t = 0; !q.empty(); t++) {
        if (ans <= t) return t;
 
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().first;
            int y = q.front().second.first;
            int z = q.front().second.second;
            q.pop();
 
            if (x == MAX - 1 && y == MAX - 1 && z == MAX - 1) {
                return t;
            }
 
            for (int d = 0; d < 6; d++) {
                int nx = x + direct[d][0];
                int ny = y + direct[d][1];
                int nz = z + direct[d][2];
 
                if (nx < 0 || ny < 0 || nz < 0 || nx >= MAX || ny >= MAX || nz >= MAX) continue;
                if (visit[nx][ny][nz] || !map[nx][ny][nz]) continue;
 
                q.push({ nx,{ny,nz} });
                visit[nx][ny][nz] = true;
            }
        }
    }
 
    return -1;
}
 
bool rotate(int idx) {
    int tmp[MAX][MAX][MAX] = { 0, };
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            tmp[idx][i][j] = map[idx][j][MAX - 1 - i];
        }
    }
 
    int cnt = 0;
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (map[idx][i][j] == tmp[idx][i][j]) cnt++;
            map[idx][i][j] = tmp[idx][i][j];
        }
    }
 
    if (cnt == MAX * MAX) return false;
    else return true;
}
 
void dfs(int idx) {
    if (idx == MAX) {
        if (!map[MAX - 1][MAX - 1][MAX - 1]) {
            return;
        }
 
        int ret = bfs();
        if (ret != -1) {
            ans = min(ans, ret);
        }
 
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        if (map[0][0][0]) {
            dfs(idx + 1);
            if (ans == MIN_ANS) return;
        }
 
        if (!rotate(idx)) return;
    }
}
 
void copyArray() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < MAX; k++) {
                map[order[i]][j][k] = list[i][j][k];
            }
        }
    }
}
 
void func() {
    ans = 1e9;
    do {
        copyArray();
        dfs(0);
    } while (next_permutation(order, order + MAX));
 
    if (ans == 1e9) ans = -1;
    cout << ans << '\n';
}
 
void input() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < MAX; k++) {
                cin >> list[i][j][k];
            }
        }
        order[i] = i;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 14497 주난의 난(難)  (0) 2024.06.21
boj 2132 나무 위의 벌레  (0) 2024.06.17
boj 14466 소가 길을 건너간 이유 6  (0) 2022.10.13
boj 18112 이진수 게임  (0) 2022.09.16
boj 16946 벽 부수고 이동하기 4  (0) 2022.05.22

+ Recent posts

티스토리툴바