문제

 

풀이

주어진 배열에서 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

www.acmicpc.net/problem/3085

 

3085번: 사탕 게임

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

www.acmicpc.net

N * N 크기에 사탕이 채워져있는데 여기서 인접한 사탕 2개를 교환합니다.

그 후에 N * N 크기의 배열에서 사탕의 색이 같은색으로 이루어진 가장 긴 연속된 부분을 찾아야합니다.

 

이 문제는 모든 경우를 다 해봐야하므로 이중for문을 돌려주었고, 4방향 탐색을 하여 하나씩 교환을 하고, 행, 열에서 연속된 사탕의 최대 갯수를 구하였습니다.

 

 

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
#include <iostream>
#include <algorithm>
using namespace std;
 
char list[51][51];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, ans;
 
void solve() {
    for (int i = 0; i < N; i++) {
        int cnt = 1;
        for (int j = 1; j < N; j++) {
            if (list[i][j] == list[i][j - 1]) cnt++;
            else {
                ans = max(ans, cnt);
                cnt = 1;
            }
        }
        ans = max(ans, cnt);
    }
 
    for (int j = 0; j < N; j++) {
        int cnt = 1;
        for (int i = 1; i < N; i++) {
            if (list[i][j] == list[i - 1][j]) cnt++;
            else {
                ans = max(ans, cnt);
                cnt = 1;
            }
        }
        ans = max(ans, cnt);
    }
}
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            char ch = list[i][j];
            for (int k = 0; k < 4; k++) {
                int nx = i + direct[k][0];
                int ny = j + direct[k][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
 
                swap(list[i][j], list[nx][ny]);
                solve();
                swap(list[i][j], list[nx][ny]);
            }
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 2564 경비원  (0) 2021.04.13
boj 16719 ZOAC  (0) 2021.03.15
boj 8320 직사각형을 만드는 방법  (0) 2021.02.25
boj 3985 롤 케이크  (0) 2021.02.25
boj 2116 주사위 쌓기  (0) 2021.02.25

www.acmicpc.net/problem/2116

 

2116번: 주사위 쌓기

첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는

www.acmicpc.net

주사위를 순서대로 쌓는데 i번 주사위의 윗면의 숫자와 i + 1번 주사위의 아랫면 숫자가 같아야합니다.

우선 rlist에 반대편 인덱스를 모두 저장해줍니다.

그 다음 0 ~ 5번 인덱스가 밑면일 경우를 다 구해서 각각의 최댓값을 갱신시켜주면 됩니다.

 

i번이 맨밑 인덱스라고 하면 반대 인덱스인 rx를 가져올수 있고, 이 두개를 제외한 나머지 숫자 중 max값을 찾아서 다음 인덱스로 재귀를 돌려주시면 됩니다.

이때 재귀를 돌릴 때 유지하는 값은 인덱스, 위에있는 값 (맞춰야하는 값), 현재까지 주사위의 최대 합입니다.

 

 

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
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
 
int list[10000][6], rlist[6];
int N, ans;
 
void init() {
    rlist[0] = 5;
    rlist[5] = 0;
 
    rlist[1] = 3;
    rlist[3] = 1;
 
    rlist[2] = 4;
    rlist[4] = 2;
}
 
void dfs(int idx, int value, int sum) {
    if (idx == N) {
        ans = max(ans, sum);
        return;
    }
 
    for (int i = 0; i < 6; i++) {
        if (list[idx][i] == value) {
            int rx = rlist[i];
 
            int max_value = 0;
            for (int j = 0; j < 6; j++) {
                if (j == i || j == rx) continue;
 
                max_value = max(max_value, list[idx][j]);
            }
 
            dfs(idx + 1, list[idx][rx], sum + max_value);
            break;
        }
    }
}
 
void func() {
    for (int i = 0; i < 6; i++) {
        int rx = rlist[i];
 
        int max_value = 0;
        for (int j = 0; j < 6; j++) {
            if (j == i || j == rx) continue;
 
            max_value = max(max_value, list[0][j]);
        }
 
        dfs(1, list[0][rx], max_value);
    }
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 6; j++) cin >> list[i][j];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    input();
    func();
    cout << ans << '\n';
 
    return 0;
}
 cs

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

boj 8320 직사각형을 만드는 방법  (0) 2021.02.25
boj 3985 롤 케이크  (0) 2021.02.25
boj 10163 색종이  (0) 2021.02.24
boj 20055 컨베이어 벨트 위의 로봇  (0) 2021.02.23
boj 2331 반복수열  (0) 2021.02.23

www.acmicpc.net/problem/17281

 

17281번: ⚾

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종

www.acmicpc.net

입력으로 이닝 수가 주어지고 다음 줄에는 각 이닝에서 1~9번의 선수들이 공을 쳤을 때 나오는 경우가 주어집니다.

안타 : 1

2루타 : 2

3루타 : 3

홈런 : 4

아웃 : 0

우선 1번이 무조건 4번타자이므로 1번을 제외한 2번~9번까지 브루트포스 방식으로 순열을 구합니다.

저는 cnt가 3이되면 그다음은 무조건 1번선수를 넣었습니다.

 

그 다음 게임을 시작합니다.

g : 이닝 수

t : 현재 타자

out : 아웃 수 (3 out이면 이닝 종료)

x : 현재 타자의 결과

 

저는 ground배열로 1~3루 나가있는 선수를 체크하였고, ground[3]은 점수입니다.

x가 1이면 안타이므로 모두 1칸씩 이동합니다.

x가 2이면 2루타이므로 모두 2칸씩 이동합니다.

x가 3이면 3루타이므로 모두 3칸씩 이동합니다.

x가 4이면 홈런이므로 나가있는 선수들과 본인 포함해서 점수에 더해줍니다.

x가 0이면 아웃이므로 out을 1 늘려주고 만약 out이 3이되면 이닝 종료이므로 ground를 초기화해주고 다음 이닝으로 넘어갑니다.

여기서 이닝이 바뀌어도 현재타자는 계속 유지시켜줘야합니다.

 

위와같은 방식으로 시뮬레이션을 돌려서 max점수를 출력해주시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer> order = new ArrayList<>();
    static boolean visit[];
    static int list[][];
    static int N, ans;
 
    static void game() {
        int ground[] = new int[4];
        int g = 0;
        int t = 0;
        int out = 0;
        while (g < N) {
            int x = list[g][order.get(t)];
 
            if (x == 1) {
                ground[3] += ground[2];
                ground[2] = 0;
                ground[2] += ground[1];
                ground[1] = 0;
                ground[1] += ground[0];
                ground[0] = 1;
            } else if (x == 2) {
                ground[3] += ground[2];
                ground[2] = 0;
                ground[3] += ground[1];
                ground[1] = 0;
                ground[2] += ground[0];
                ground[1] = 1;
                ground[0] = 0;
            } else if (x == 3) {
                ground[3] += ground[2];
                ground[3] += ground[1];
                ground[3] += ground[0];
                ground[1] = 0;
                ground[0] = 0;
                ground[2] = 1;
            } else if (x == 4) {
                int sum = 1;
                for (int i = 0; i <= 2; i++) {
                    if (ground[i] == 1) {
                        ground[i] = 0;
                        sum++;
                    }
                }
                ground[3] += sum;
            } else {
                out++;
                if (out == 3) {
                    ground[2] = 0;
                    ground[1] = 0;
                    ground[0] = 0;
                    out = 0;
                    g++;
                }
            }
            t = (t + 1) % 9;
        }
 
        ans = Math.max(ans, ground[3]);
    }
 
    static void func(int cnt) {
        if (cnt == 9) {
            game();
            return;
        }
 
        if (cnt == 3) {
            order.add(0);
            func(4);
            order.remove(cnt);
        }
 
        for (int i = 1; i < 9; i++) {
            if (visit[i])
                continue;
 
            visit[i] = true;
            order.add(i);
            func(cnt + 1);
            order.remove(cnt);
            visit[i] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][9];
        visit = new boolean[10];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0);
        System.out.println(ans);
    }
}
 cs

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

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

www.acmicpc.net/problem/3040

 

3040번: 백설 공주와 일곱 난쟁이

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.

www.acmicpc.net

부르트포스 방식으로 9개 중 7개를 뽑는 과정에서 7개의 합이 100이 되면 뽑은 수들을 출력하면 되는 문제입니다.

9개중 7개를 뽑는다고 명시가 되어있으니 조합으로 해결해야하고, 7개를 뽑았을 때 합이 100인 수들을 출력하면 됩니다.

7개를 뽑았으나 합이 100이 아닌경우에 그냥 리턴을 시켜주시면 되고, 재귀를 돌릴때 다음 매개변수 sum이 100보다 크면 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> ans = new ArrayList<>();
    static int list[] = new int[9];
 
    static void func(int idx, int cnt, int sum) {
        if (cnt == 7) {
            if (sum != 100)
                return;
 
            for (int i = 0; i < 7; i++) {
                sb.append(ans.get(i) + "\n");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = idx; i < 9; i++) {
            if (sum + list[i] > 100)
                continue;
            
            ans.add(list[i]);
            func(i + 1, cnt + 1, sum + list[i]);
            ans.remove(cnt);
        }
    }
 
    static void input() throws Exception {
        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0, 0);
        System.out.println(sb.toString());
    }
}
 cs

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

boj 14456 Hoof, Paper, Scissors (Bronze)  (0) 2022.12.30
boj 17281 ⚾  (0) 2021.02.16
boj 2961 도영이가 만든 맛있는 음식  (0) 2021.02.15
boj 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데  (0) 2021.01.29
boj 1018 체스판 다시 칠하기  (0) 2021.01.29

www.acmicpc.net/problem/2961

 

2961번: 도영이가 만든 맛있는 음식

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은

www.acmicpc.net

브루트포스 방식으로 모든 경우를 다 계산해주시면 됩니다.

N개 중에 뽑는 갯수가 정해져있지 않기때문에 조합이 아닌 부분집합으로 재료를 고를때마다 ans를 갱신해줍니다.

 

 

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
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 long list[][];
    static long ans = Long.MAX_VALUE;
    static int N;
 
    static void func(int idx, long a, long b) {
        if (idx > 0)
            ans = Math.min(ans, Math.abs(a - b));
        
        if (idx == N)
            return;
 
        for (int i = idx; i < N; i++) {
            func(i + 1, a * list[i][0], b + list[i][1]);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new long[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Long.parseLong(st.nextToken());
            list[i][1] = Long.parseLong(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 1, 0);
        System.out.println(ans);
    }
}
 cs

 

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

boj 17281 ⚾  (0) 2021.02.16
boj 3040 백설 공주와 일곱 난쟁이  (0) 2021.02.15
boj 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데  (0) 2021.01.29
boj 1018 체스판 다시 칠하기  (0) 2021.01.29
boj 15686 치킨 배달  (0) 2021.01.22

www.acmicpc.net/problem/14502

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

연구소에 벽 3개를 설치하여 바이러스로부터 안전 영역의 크기를 최대로 해야합니다.

이 문제는 브루트포스 방식과 bfs를 사용하여 해결하였습니다.

 

브루트포스로 설치할 벽의 모든 경우를 구하였고, 3개의 벽을 설치하면 bfs를 돌려서 바이러스를 최대한 퍼뜨린 후에 안전 영역의 갯수를 구하였습니다.

 

 

[C++]

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
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
 
queue<pair<int, int> > q;
int direct[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
bool visit[8][8];
int list[8][8];
int N, M, ans;
 
void bfs() {
    queue<pair<int, int> > nq = q;
    int sum = 0;
    while (!nq.empty()) {
        int x = nq.front().first;
        int y = nq.front().second;
        nq.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (list[nx][ny] != 0 || visit[nx][ny]) continue;
            visit[nx][ny] = true;
            nq.push({ nx,ny });
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (list[i][j] != 0 || visit[i][j]) continue;
            sum++;
        }
    }
 
    ans = max(ans, sum);
}
 
void func(int x, int y, int cnt) {
    if (cnt == 3) {
        bfs();
        memset(visit, false, sizeof(visit));
        return;
    }
 
    int sx = x;
    int sy = y;
    for (int i = sx; i < N; i++) {
        for (int j = sy; j < M; j++) {
            if (list[i][j] != 0) continue;
 
            list[i][j] = 1;
            if (j == M - 1) func(i + 1, 0, cnt + 1);
            else func(i, j + 1, cnt + 1);
            list[i][j] = 0;
        }
        sy = 0;
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
 
            if (list[i][j] == 2) {
                q.push({ i,j });
                visit[i][j] = true;
            }
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func(0, 0, 0);
    cout << ans << '\n';
 
    return 0;
}
cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[8][8];
    static Deque<int[]> virus = new ArrayDeque<>();
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, ans;
 
    static void bfs() {
        Deque<int[]> dq = new ArrayDeque<>();
        boolean visit[][] = new boolean[8][8];
        dq.addAll(virus);
        Iterator<int[]> iter = dq.iterator();
        while (iter.hasNext()) {
            int xy[] = iter.next();
            visit[xy[0]][xy[1]] = true;
        }
 
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (visit[nx][ny] || list[nx][ny] == 1)
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
 
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visit[i][j] || list[i][j] != 0)
                    continue;
 
                cnt++;
            }
        }
 
        ans = Math.max(ans, cnt);
    }
 
    static void func(int sx, int sy, int cnt) {
        if (cnt == 3) {
            bfs();
            return;
        }
 
        int i = sx;
        int j = sy;
        for (; i < N; i++) {
            for (; j < M; j++) {
                if (list[i][j] != 0)
                    continue;
 
                list[i][j] = 1;
                if (j == M - 1)
                    func(i + 1, 0, cnt + 1);
                else
                    func(i, j + 1, cnt + 1);
                list[i][j] = 0;
            }
            j = 0;
        }
    }
 
    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());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == 2) {
                    virus.add(new int[] { i, j });
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0, 0);
        System.out.println(ans);
    }
}
cs

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

boj 10026 적록색약  (0) 2021.02.13
boj 2206 벽 부수고 이동하기  (0) 2021.02.13
boj 20304 비밀번호 제작  (0) 2021.02.08
boj 2606 바이러스  (0) 2021.02.03
boj 1012 유기농 배추  (0) 2021.02.03

www.acmicpc.net/problem/17406

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

앞의 배열 돌리기1, 2와 같이 배열이 주어지고 이 문제는 회전시킬 구간이 추가로 주어집니다.

구간은 r c s 이렇게 들어오는데 구간 (r - s, c - s) ~ (r + s, c + s)를 1번 회전시켜라는 뜻입니다.

하지만 이 연산 순서를 임의로 정해서 배열 A의 값을 최소로 해야하는 문제입니다.

즉, 구간정보를 브루트포스방식을 사용하여 모든 순서로 연산을 다 해봐야합니다.

 

연산 순서는 ArrayList를 활용하여 구간을 넣었다 뺐다 하는 방식으로 정하였고, 순서를 모두 정하면 list의 값을 복사한 다른 배열을 선언하여 모든 회전을 수행한 후에 A의 최솟값을 구하였습니다.

 

회전 로직은 1번, 2번과 같지만 구간에 해당하는 숫자가 1개인 경우 next로 자신으로 설정하는 예외처리를 해주었습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int direct[][] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
    static ArrayList<int[]> rotate = new ArrayList<>();
    static ArrayList<int[]> rotatesolve = new ArrayList<>();
    static boolean visit[][], chk[];
    static int list[][], clist[][];
    static int N, M, K, r, c, s;
    static int sx, sy, ex, ey, ans = Integer.MAX_VALUE;
 
    static void print() {
        System.out.println(ans);
    }
 
    static int dfs(int x, int y, int idx) {
        visit[x][y] = true;
 
        int nx = x + direct[idx][0];
        int ny = y + direct[idx][1];
 
        if (nx < sx || ny < sy || nx > ex || ny > ey) {
            idx++;
            nx = x + direct[idx][0];
            ny = y + direct[idx][1];
            if (nx < sx || ny < sy || nx > ex || ny > ey) {
                nx = x;
                ny = y;
            }
        }
 
        if (visit[nx][ny]) {
            int tmp = clist[x][y];
            clist[x][y] = clist[nx][ny];
            return tmp;
        }
 
        int tmp = clist[x][y];
        clist[x][y] = dfs(nx, ny, idx);
        return tmp;
    }
 
    static void solve(int rr, int cc, int ss) {
        sx = rr - ss;
        sy = cc - ss;
        ex = rr + ss;
        ey = cc + ss;
 
        for (int i = 0;; i++) {
            dfs(sx, sy, 0);
            sx++;
            sy++;
            ex--;
            ey--;
            if (sx > ex || sy > ey)
                break;
        }
 
        for (int i = rr - ss; i <= rr + ss; i++) {
            Arrays.fill(visit[i], false);
        }
    }
 
    static void func(int cnt) {
        if (cnt == K) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++)
                    clist[i][j] = list[i][j];
            }
            for (int i = 0; i < K; i++) {
                solve(rotatesolve.get(i)[0], rotatesolve.get(i)[1], rotatesolve.get(i)[2]);
            }
 
            for (int i = 1; i <= N; i++) {
                int sum = 0;
                for (int j = 1; j <= M; j++) {
                    sum += clist[i][j];
                }
                ans = Math.min(ans, sum);
            }
 
            return;
        }
 
        for (int i = 0; i < K; i++) {
            if (chk[i])
                continue;
 
            rotatesolve.add(rotate.get(i));
            chk[i] = true;
            func(cnt + 1);
            chk[i] = false;
            rotatesolve.remove(cnt);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        list = new int[N + 1][M + 1];
        clist = new int[N + 1][M + 1];
        visit = new boolean[N + 1][M + 1];
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());
            rotate.add(new int[] { r, c, s });
        }
 
        chk = new boolean[K];
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0);
        print();
    }
}
 cs

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

boj 1987 알파벳  (0) 2021.02.18
boj 3109 빵집  (0) 2021.02.18
boj 16927 배열 돌리기 2  (0) 2021.02.10
boj 16926 배열 돌리기 1  (0) 2021.02.10
boj 1068 트리  (0) 2021.02.09

www.acmicpc.net/problem/2422

 

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번

www.acmicpc.net

섞으면 안되는 조합이 입력으로 주어지고 3개 조합이 가능한 방법이 몇 개 있는지 출력하는 문제입니다.

 

저는 섞으면 안되는 조합을 2차원배열로 표시하였습니다.

조합이 x, y로 주어지면

visit[x][y] = true;

visit[y][x] = true;

여기서 true로 표시하는 것은 x번과 y번은 섞으면 안되는 조합이라는 것입니다.

 

그 다음 재귀를 돌리는데 매개변수를 pre(이전에 골랐던 번호), now(방금 고른 번호), cnt(고른 갯수)로 하였고

반복문으로 마지막 고를 번호 i를 고릅니다.

 

i를 고를 때 첫번째로 고른 pre와 두번째로 고른 now와 섞으면 안되는 조합인지 확인한 후에 다음으로 넘겨줍니다.

 

마지막으로 3개를 모두 골랐으면 ans를 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
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 boolean noMix[][];
    static int N, M, ans;
 
    static void func(int pre, int now, int cnt) {
        if (cnt == 3) {
            ans++;
            return;
        }
 
        for (int i = now + 1; i <= N; i++) {
            if (noMix[now][i])
                continue;
            if (pre != -1 && noMix[pre][i])
                continue;
 
            func(now, i, cnt + 1);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        noMix = new boolean[N + 1][N + 1];
        int x, y;
 
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            noMix[x][y] = true;
            noMix[y][x] = true;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(-1, 0, 0);
        System.out.println(ans);
    }
}
cs

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

boj 17281 ⚾  (0) 2021.02.16
boj 3040 백설 공주와 일곱 난쟁이  (0) 2021.02.15
boj 2961 도영이가 만든 맛있는 음식  (0) 2021.02.15
boj 1018 체스판 다시 칠하기  (0) 2021.01.29
boj 15686 치킨 배달  (0) 2021.01.22

www.acmicpc.net/problem/1018

 

1018번: 체스판 다시 칠하기

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

브루트포스 문제로 8*8 크기씩 계속 비교해가며 다시 칠해야할 갯수의 최솟값을 구해야합니다.

 

cnt1 => 맨 왼쪽 위 칸이 B로 칠해질 경우

cnt2 => 맨 왼쪽 위 칸이 W로 칠해질 경우

 

cnt1의 경우에는 i가 짝수일 때 BWBWBWBW, 홀수일 때 WBWBWBWB를 만들어야 합니다.

cnt2의 경우에는 i가 짝수일 때 WBWBWBWB, 홀수일 때 BWBWBWBW를 만들어야 합니다.

 

각 인덱스에서 다른색이 칠해져있으면 해당cnt를 증가시켜줍니다.

이 과정을 8*8 크기만큼 반복하여 최솟값을 출력합니다.

 

 

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
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 char ch[][];
    static int N, M, ans = 2500;
 
    static void func(int x, int y) {
        int cnt1 = 0;
        int cnt2 = 0;
        for (int i = x; i < x + 8; i++) {
            for (int j = y; j < y + 8; j++) {
                if (i % 2 == 0) {
                    if (j % 2 == 0) {
                        if (ch[i][j] == 'B')
                            cnt2++;
                        else
                            cnt1++;
                    } else {
                        if (ch[i][j] == 'B')
                            cnt1++;
                        else
                            cnt2++;
                    }
                } else {
                    if (j % 2 == 0) {
                        if (ch[i][j] == 'B')
                            cnt1++;
                        else
                            cnt2++;
                    } else {
                        if (ch[i][j] == 'B')
                            cnt2++;
                        else
                            cnt1++;
                    }
                }
            }
        }
 
        ans = Math.min(ans, Math.min(cnt1, cnt2));
    }
 
    static void solve() {
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                func(i, j);
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ch = new char[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            ch[i] = st.nextToken().toCharArray();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        solve();
    }
}
 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 15686 치킨 배달  (0) 2021.01.22

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

 

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고

www.acmicpc.net

바이러스의 위치들을 저장해놓고 활성할 바이러스를 부르트포스로 정하여 bfs로 바이러스가 퍼지는 최소 시간을 구하는 문제입니다.

바이러스가 모두 퍼졌는지에 대한 확인은 처음 0의 갯수(zero) == 전염된 0의 갯수(viruson)으로 확인하였고,

7번 예제와 같이 입력 값으로 빈칸이 주어지지 않은 경우에는

예외처리로 벽의 갯수(wall) + 바이러스의 위치(virus.size()) == N*N으로 확인하였습니다.

마지막에 비활성화 바이러스만 남아도 모두 전염된 것으로 보기 때문에 d배열에서 해당 위치가 빈칸일 경우에만 시간비교를 하였습니다.

 

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
 
vector<pair<int, int> > virus, op;
int list[50][50], d[50][50], N, M, ans = -1, wall, viruson, zero;
int direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
bool visit[50][50], chk[10];
 
void bfs() {
    memset(d, 0, sizeof(d));
    memset(visit, false, sizeof(visit));
    viruson = 0;
 
    int virusoff = virus.size() - M;
    queue<pair<pair<int, int>, int> > q;
    for (int i = 0; i < op.size(); i++) {
        q.push({ op[i], 0 });
        visit[op[i].first][op[i].second] = true;
    }
 
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (list[nx][ny] == 1 || visit[nx][ny]) continue;
 
            q.push({ {nx,ny},cnt + 1 });
            visit[nx][ny] = true;
            d[nx][ny] = d[x][y] + 1;
            if (list[nx][ny] == 0) viruson++;
        }
    }
 
    if (zero == viruson) {
        int movetime = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (list[i][j]) continue;
 
                movetime = max(movetime, d[i][j]);
            }
        }
 
        if (ans == -1) ans = movetime;
        else ans = min(ans, movetime);
    }
}
 
void func(int idx, int cnt) {
    if (cnt == M) {
        bfs();        
        return;
    }
 
    for (int i = idx; i < virus.size(); i++){
        if (chk[i]) continue;
 
        op.push_back(virus[i]);
        chk[i] = true;
        func(i + 1, cnt + 1);
        chk[i] = false;
        op.pop_back();
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
            if (list[i][j] == 2) {
                virus.push_back({ i,j });
            }
            else if (list[i][j]) {
                wall++;
            }
            else zero++;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    if (wall + virus.size() == N*N) ans = 0;
    else func(0, 0);
    cout << ans << '\n';
 
    return 0;
}
cs

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

boj 20419 화살표 미로 (Easy)  (0) 2021.01.23
boj 2638 치즈  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22
boj 3055 탈출  (0) 2021.01.22

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

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

M개의 치킨집을 골라 도시의 치킨거리 합을 최소로 해야합니다.

인덱스를 이용하여 집의 좌표와 치킨집의 좌표를 각각 저장해놓습니다.

그 다음 모든 가능한 경우를 구해야하기 때문에 조합으로 고른 치킨집의 인덱스를 pick 배열에 저장하여

M개를 골랐으면 집과 고른 치킨집의 거리를 N^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
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[][], house[][], chicken[][], pick[][];
    static int N, M, hsize, csize, ans = Integer.MAX_VALUE;
 
    static void func(int idx, int cnt) {
        if (cnt == M) {
            int sum = 0;
            for (int i = 0; i < hsize; i++) {
                int dis = Integer.MAX_VALUE;
                for (int j = 0; j < M; j++) {
                    int x = house[i][0] - pick[j][0];
                    int y = house[i][1] - pick[j][1];
                    dis = Math.min(dis, Math.abs(x) + Math.abs(y));
                }
                sum += dis;
            }
 
            ans = Math.min(ans, sum);
            return;
        }
 
        for (int i = idx; i < csize; i++) {
            pick[cnt][0] = chicken[i][0];
            pick[cnt][1] = chicken[i][1];
            func(i + 1, cnt + 1);
            pick[cnt][0] = 0;
            pick[cnt][1] = 0;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N][N];
        house = new int[100][2];
        chicken = new int[13][2];
        pick = new int[13][2];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == 1) {
                    house[hsize][0] = i;
                    house[hsize++][1] = j;
                } else if (list[i][j] == 2) {
                    chicken[csize][0] = i;
                    chicken[csize++][1] = j;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0);
        System.out.println(ans);
    }
}
 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

+ Recent posts

티스토리툴바