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

 

오븐의 깊이에 따라 피자가 들어갈 수 있는 크기가 다릅니다.

오븐에 피자를 위에서부터 차례대로 쌓는 방식인데 중간에 크기가 좁은 오븐을 만나면 더이상 내려갈 수 없습니다.

따라서 오븐의 크기를 먼저 조정해줄 수 있습니다.

 

5 6 4 3 6 2 3

오븐의 크기가 위에서부터 이렇게 주어진다면

위에서부터 최솟값을 갱신한다면

 

5 5 4 3 3 2 2

이렇게 바뀌게되고, 크기가 같거나 작아지는 수열이 됩니다.

그러면 위에서부터 크기가 맞는 높이를 계속 찾아줄 필요 없이 밑에서부터 맞는 크기를 찾아주면 됩니다.

N에서 시작하여 피자가 들어갈 수 있는 높이라면 바로 넣어주는 방식으로 해결할 수 있습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 300001
using namespace std;
 
int width[MAX];
int list[MAX];
int N, M;
 
void func() {
    int idx = N;
    for (int i = 0; i < M; i++) {
        bool flag = false;
        while (idx > 0) {
            if (width[idx] >= list[i]) {
                idx--;
                flag = true;
                break;
            }
            idx--;
        }
        if (!flag) {
            cout << "0\n";
            return;
        }
    }
    cout << idx + 1 << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> width[i];
        if (i > 1) {
            width[i] = min(width[i], width[i - 1]);
        }
    }
 
    for (int i = 0; i < M; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 3758 KCPC  (0) 2024.06.09
boj 17143 낚시왕  (0) 2021.04.23
boj 20207 달력  (0) 2021.04.22
boj 17144 미세먼지 안녕!  (0) 2021.04.14
boj 2564 경비원  (0) 2021.04.13

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

 

구현문제는 문제만 잘 읽고 이해한다면 어렵지 않게 해결할 수 있습니다.

물론 저는 읽고 이해하는게 어렵습니다 ^^

 

팀 순위를 정하는 방식은

각 문제들을 해결하면서 얻은 점수의 합이 되겠고,

최종 점수가 같으면 풀이를 제출한 횟수가 적은 팀이 우선
제출 횟수도 같으면 마지막 제출 시간이 더 빠른 팀이 우선순위를 높게 가져갑니다.

 

그렇다면 입력단계에서 구해야할건

먼저 점수의 합은 입력으로 들어온 각 팀마다 문제별 최고점수를 저장하면 구할 수 있고,

제출한 횟수는 팀이 입력되는 횟수를 카운팅하여 구할 수 있고,

마지막 제출 시간은 입력들의 인덱스를 갱신하기만 하면 구할 수 있습니다.

 

이제 위에서 구한 정보들로 순위를 정할 수 있습니다.

문제에서는 본인의 순위만 출력하면 되기 때문에 본인보다 순위가 높은 팀을 카운팅하면 구할 수 있습니다.

 

위에서 언급한 팀 순위를 정하는 방식을 이용하여 특정 팀이 본인보다 높은지 확인해주시면 되겠습니다.

 

 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 101
using namespace std;
 
int scores[MAX][MAX];
int tries[MAX];
int cnts[MAX];
int N, K, T, M;
 
int getScore(int team) {
    int ret = 0;
    for (auto score : scores[team]) {
        ret += score;
    }
    return ret;
}
 
bool isBetter(int team) {
    int x = getScore(T);
    int y = getScore(team);
    if (x == y) {
        if (cnts[T] == cnts[team]) return tries[T] > tries[team];
        return cnts[T] > cnts[team];
    }
    return x < y;
}
 
void func() {
    int ret = 0;
    for (int i = 1; i <= N; i++) {
        if (i == T) continue;
        ret += isBetter(i);
    }
    cout << ret + 1 << '\n';
}
 
void input() {
    int id, no, s;
    cin >> N >> K >> T >> M;
    for (int i = 1; i <= M; i++) {
        cin >> id >> no >> s;
        scores[id][no] = max(scores[id][no], s);
        cnts[id]++;
        tries[id] = i;
    }
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        memset(scores[i], 0, sizeof(scores[i]));
    }
    memset(cnts, 0, sizeof(cnts));
    memset(tries, 0, sizeof(tries));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
        init();
    }
 
    return 0;
}
 cs

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

boj 1756 피자 굽기  (0) 2024.08.08
boj 17143 낚시왕  (0) 2021.04.23
boj 20207 달력  (0) 2021.04.22
boj 17144 미세먼지 안녕!  (0) 2021.04.14
boj 2564 경비원  (0) 2021.04.13

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

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

1초 동안 다음과 같은 일이 일어납니다.

1. 미세먼지가 확산되며 미세먼지가 있는 모든 칸에서 동시에 일어납니다.

 - 인접한 4방향으로 확산됩니다.

 - 인접한 방향이 맵 밖이거나 공기청정기가 있는 곳이라면 확산이 일어나지 않습니다.

 - 확산되는 양은 list[i][j] / 5입니다. (소수점 버림)

 - (i, j)에 남은 미세먼지 양은 list[i][j] - (list[i][j] / 5) * (확산된 방향의 갯수)입니다.

2. 공기청정기가 작동됩니다.

 - 위쪽 공기청정기의 바람은 반시계방향으로 순환, 아래쪽 공기청정기의 바람은 시계방향으로 순환합니다.

 - 미세먼지가 바람의 방향대로 한 칸씩 이동합니다.

 - 공기청정기로 들어가는 미세먼지는 정화됩니다.

 

위의 모든것을 직접 구현해야합니다.

 

우선 2중for문을 돌면서 미세먼지를 확산시킵니다. 이 때 확산이 동시에 일어나야하므로 nextlist라는 변수를 사용하였습니다.

그 다음 공기청정기를 작동시켜 위쪽에는 반시계방향으로, 아래쪽에는 시계방향으로 값을 회전시켜줍니다.

이 과정을 T번 반복하여 T초 후 남아있는 미세먼지 양을 출력합니다.

 

 

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.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[51][51];
    static int nextlist[][] = new int[51][51];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int cleaner[][] = new int[2][2];
    static int N, M, T;
 
    static void clear() {
        int x = cleaner[0][0];
        int y = cleaner[0][1];
 
        x--;
        int d = 3;
        while (true) {
            int nx = x + direct[d][0];
            int ny = y + direct[d][1];
 
            if (nx <= 0 || ny <= 0 || nx > cleaner[0][0] || ny > M) {
                d = (d + 1) % 4;
                continue;
            }
            list[x][y] = 0;
            if (list[nx][ny] == -1)
                break;
 
            list[x][y] = list[nx][ny];
            x = nx;
            y = ny;
        }
 
        x = cleaner[1][0];
        y = cleaner[1][1];
 
        x++;
        d = 1;
        while (true) {
            int nx = x + direct[d][0];
            int ny = y + direct[d][1];
 
            if (nx < cleaner[1][0] || ny <= 0 || nx > N || ny > M) {
                d = (d + 3) % 4;
                continue;
            }
            list[x][y] = 0;
            if (list[nx][ny] == -1)
                break;
 
            list[x][y] = list[nx][ny];
            x = nx;
            y = ny;
        }
    }
    
    static void spread() {
        for (int i = 1; i <= N; i++)
            Arrays.fill(nextlist[i], 0);
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] > 0) {
                    int diff = list[i][j] / 5;
                    int cnt = 0;
                    for (int d = 0; d < 4; d++) {
                        int nx = i + direct[d][0];
                        int ny = j + direct[d][1];
 
                        if (nx <= 0 || ny <= 0 || nx > N || ny > M)
                            continue;
                        if (list[nx][ny] == -1)
                            continue;
 
                        nextlist[nx][ny] += diff;
                        cnt++;
                    }
 
                    nextlist[i][j] += (list[i][j] - diff * cnt);
                }
            }
        }
        
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] == -1)
                    continue;
                list[i][j] = nextlist[i][j];
            }
        }
    }
 
    static void func() {
        for (int t = 1; t <= T; t++) {
            spread();
            clear();
        }
    }
 
    static void print() {
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] > 0)
                    ans += list[i][j];
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int t = 0;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        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());
                if (list[i][j] == -1) {
                    cleaner[t][0] = i;
                    cleaner[t++][1] = j;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}
 cs

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

boj 17143 낚시왕  (0) 2021.04.23
boj 20207 달력  (0) 2021.04.22
boj 2564 경비원  (0) 2021.04.13
boj 16719 ZOAC  (0) 2021.03.15
boj 3085 사탕 게임  (0) 2021.02.26

www.acmicpc.net/problem/2564

 

2564번: 경비원

첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄

www.acmicpc.net

시작점과 도착점 모두 가장자리에 있으며, 가장자리로만 인접한 좌표로 이동할 수 있습니다.

 

입력은 상점의 위치와 기준점에서의 거리가 주어집니다.

1 -> 북쪽

2 -> 남쪽

3 -> 서쪽

4 -> 동쪽

이렇게 위치하며

북쪽과 남쪽의 경우 왼쪽에서의 거리, 서쪽과 동쪽의 경우 위쪽에서의 거리를 나타냅니다.

 

10 5
3
1 4
3 2
2 8
2 3

즉 위의 케이스로는

(1, 4) : 북쪽이고, 왼쪽에서 4칸 떨어진 거리

(3, 2) : 서쪽이고, 위쪽에서 2칸 떨어진 거리

(2, 8) : 남쪽이고, 왼쪽에서 8칸 떨어진 거리

(2, 3) : 남쪽이고, 왼쪽에서 3칸 떨어진 거리

 

이제 모든 경우를 다 생각하여 계산해주시면 됩니다. (시작점 : (sp, sd), 도착점 : (ep, ed))

우선 시작점과 도착점의 위치(방향)이 같을 때(sp == ep)는 거리의 차이를 더합니다.

다음은 sp의 값에 따라 if문을 모두 추가하였습니다.

방향이 인접한 방향의 경우에는 각 상대방향 쪽으로 이동하는 것이 최소거리입니다.

방향이 인접한 방향이 아니라면 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
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[101][2];
    static int N, M, K, sp, sd, ans;
 
    static void func() {
        for (int i = 0; i < K; i++) {
            int ep = list[i][0];
            int ed = list[i][1];
 
            if (sp == ep)
                ans += Math.abs(sd - ed);
            else if (sp == 1) {
                if (ep == 2) {
                    ans += Math.min(M + sd + ed, M + N - sd + N - ed);
                } else if (ep == 3) {
                    ans += (sd + ed);
                } else {
                    ans += (N - sd + ed);
                }
            } else if (sp == 2) {
                if (ep == 1) {
                    ans += Math.min(M + sd + ed, M + N - sd + N - ed);
                } else if (ep == 3) {
                    ans += (sd + M - ed);
                } else {
                    ans += (N - sd + M - ed);
                }
            } else if (sp == 3) {
                if (ep == 1) {
                    ans += (sd + ed);
                } else if (ep == 2) {
                    ans += (M - sd + ed);
                } else {
                    ans += (Math.min(N + sd + ed, N + M - sd + M - ed));
                }
            } else {
                if (ep == 1) {
                    ans += (sd + N - ed);
                } else if (ep == 2) {
                    ans += (M - sd + N - ed);
                } else {
                    ans += (Math.min(N + sd + ed, N + M - sd + M - ed));
                }
            }
        }
        
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
 
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
 
        st = new StringTokenizer(br.readLine());
        sp = Integer.parseInt(st.nextToken());
        sd = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 20207 달력  (0) 2021.04.22
boj 17144 미세먼지 안녕!  (0) 2021.04.14
boj 16719 ZOAC  (0) 2021.03.15
boj 3085 사탕 게임  (0) 2021.02.26
boj 8320 직사각형을 만드는 방법  (0) 2021.02.25

www.acmicpc.net/problem/16719

 

16719번: ZOAC

2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로

www.acmicpc.net

문자열의 길이를 1부터 1씩 늘려가며 아직 보여주지 않은 문자 중 추가했을 때 문자열이 사전 순으로 가장 앞에 오는 문자열을 출력합니다.

 

저는 길이에 변화를 시켜가며 모든 경우를 다 확인하였습니다.

반복문을 통해 아직 추가하지 않은 문자를 포함한 문자열을 모두 벡터에 넣습니다. 이 때 추가한 문자열의 방문체크를 위해 인덱스를 추가합니다.

그 중 사전 순으로 가장 앞에 오는 문자열을 출력하고, 그 문자열에서 추가한 문자의 인덱스를 가져와 방문체크를 합니다.

 

문자열의 길이가 1 ~ size 가 될때까지 반복합니다.

 

 

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
vector<pair<string, int> > v;
bool visit[110];
string str;
 
void func() {
    int ssize = str.size();
    for (int i = 0; i < ssize; i++) {
        for (int j = 0; j < ssize; j++) {
            if (visit[j]) continue;
 
            string tmp = "";
            for (int k = 0; k < ssize; k++) {
                if (visit[k] || j == k) {
                    tmp += str[k];
                }
            }
 
            v.push_back({ tmp, j });
        }
        sort(v.begin(), v.end());
        cout << v[0].first << '\n';
        visit[v[0].second] = true;
        v.clear();
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> str;
    func();
 
    return 0;
}
 cs

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

boj 17144 미세먼지 안녕!  (0) 2021.04.14
boj 2564 경비원  (0) 2021.04.13
boj 3085 사탕 게임  (0) 2021.02.26
boj 8320 직사각형을 만드는 방법  (0) 2021.02.25
boj 3985 롤 케이크  (0) 2021.02.25

www.acmicpc.net/problem/14500

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

크기가 N * M인 종이에 위와 같은 테트로미노를 하나 놓습니다.

그리고 이 테트로미노는 회전, 대칭한 모양이 가능합니다.

 

한개를 놓으면 되기때문에 각 칸에서의 모든 경우를 다 체크해야합니다.

테트로미노 중 'ㅏ', 'ㅓ', 'ㅗ', 'ㅜ' 모양을 제외하면 한붓 그리기가 가능하므로 dfs로 구할 수 있습니다.

dfs로 가능한 모양들은 dfs를 돌려줘서 4칸을 방문할 때마다 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
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
#include <iostream>
#include <algorithm>
using namespace std;
 
int list[501][501];
bool visit[501][501];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, ans;
 
void dfs(int x, int y, int cnt, int sum) {
    if (cnt == 4) {
        ans = max(ans, sum);
        return;
    }
 
    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]) continue;
 
        visit[nx][ny] = true;
        dfs(nx, ny, cnt + 1, sum + list[nx][ny]);
        visit[nx][ny] = false;
    }
}
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visit[i][j] = true;
            dfs(i, j, 1, list[i][j]);
            visit[i][j] = false;
 
            if (i + 2 < N && j + 1 < M) {
                ans = max(ans, list[i][j] + list[i + 1][j] + list[i + 2][j] + list[i + 1][j + 1]);
            }
            if (i + 1 < N && j - 1 >= 0 && j + 1 < M) {
                ans = max(ans, list[i][j] + list[i + 1][j - 1] + list[i + 1][j] + list[i + 1][j + 1]);
            }
            if (i + 1 < N && j + 2 < M) {
                ans = max(ans, list[i][j] + list[i][j + 1] + list[i][j + 2] + list[i + 1][j + 1]);
            }
            if (i - 1 >= 0 && i + 1 < N && j + 1 < M) {
                ans = max(ans, list[i][j] + list[i - 1][j + 1] + list[i][j + 1] + list[i + 1][j + 1]);
            }
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 14889 스타트와 링크  (0) 2021.03.17
boj 2023 신기한 소수  (0) 2021.03.16
boj 16922 로마 숫자 만들기  (0) 2021.02.24
boj 1987 알파벳  (0) 2021.02.18
boj 3109 빵집  (0) 2021.02.18

www.acmicpc.net/problem/14719

 

14719번: 빗물

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치

www.acmicpc.net

저는 2가지 방법으로 해결하였습니다.

 

하나는 그냥 구현으로, 다른 하나는 세그먼트 트리를 이용하였습니다.

 

먼저 블록의 최대 높이를 가진 인덱스(idx)를 구합니다.

그리고 왼쪽에서 idx까지, 오른쪽에서 idx까지 순회하면서 현재 최대 높이를 갱신해주고,

만약 현재 최대높이보다 블록의 높이가 더 작으면 그 차이만큼 더해주는 방식입니다.

 

 

emoney96.tistory.com/154

 

boj 2304 창고 다각형

www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는

emoney96.tistory.com

세그먼트 트리는 위의 문제와 같은 방식입니다.

 

트리에 각 높이의 최댓값을 저장합니다.

 

그 다음 1 ~ N번 블록을 순회하면서 자신을 포함한 왼쪽, 오른쪽 중 최고 높이를 구합니다.

왼쪽 오른쪽 최고 높이 중 낮은 높이만큼 빗물이 쌓이므로 블록높이를 뺀 값을 더해줍니다.

 

 

[구현]

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

 

 

[세그먼트 트리]

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
#include <iostream>
#include <algorithm>
using namespace std;
 
int list[501], tree[2001];
int N, M;
 
int init(int node, int s, int e) {
    if (s == e) {
        return tree[node] = list[s];
    }
 
    int m = (s + e) / 2;
    return tree[node] = max(init(node * 2, s, m), init(node * 2 + 1, m + 1, e));
}
 
int query(int node, int s, int e, int l, int r) {
    if (l > e || s > r) return 0;
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    return max(query(node * 2, s, m, l, r), query(node * 2 + 1, m + 1, e, l, r));
}
 
void func() {
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int l = query(1, 1, N, 1, i);
        int r = query(1, 1, N, i + 1, N);
 
        int result = min(l, r);
 
        if (list[i] < result) {
            ans += result - list[i];
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    init(1, 1, N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 12846 무서운 아르바이트  (0) 2022.08.19
boj 1849 순열  (0) 2021.09.08
boj 2304 창고 다각형  (0) 2021.02.25
boj 14438 수열과 쿼리 17  (0) 2021.02.21
boj 13537 수열과 쿼리 1  (0) 2021.02.21

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

 

8320번: 직사각형을 만드는 방법

상근이는 변의 길이가 1인 정사각형 n개를 가지고 있다. 이 정사각형을 이용해서 만들 수 있는 직사각형의 개수는 총 몇 개일까? 두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수

www.acmicpc.net

길이가 1인 정사각형 N개를 가지고 만들 수 있는 직사각형의 갯수를 구하는 문제입니다.

이 때, N개를 모두 사용하지 않아도 됩니다.

 

저는 N개로 만들 수 있는 높이(i)가 1인 직사각형부터 높이를 1씩 늘려가며 갯수를 구하였습니다.

그럼 너비(j)는 i * j <= N 인 경우의 갯수를 세어주시면 됩니다.

 

N = 6일 때를 예로 들면

높이가 1일 때 가능한 너비 => 1, 2, 3, 4, 5, 6

높이가 2일 때 가능한 너비 => 1, 2, 3

높이가 3일 때 가능한 너비 => 1, 2

높이가 4일 때 가능한 너비 => 1

높이가 5일 때 가능한 너비 => 1

높이가 6일 때 가능한 너비 => 1

답 14??

이렇게 구할수 있지만 문제에는 직사각형 A를 회전시켜서 B를 만들 수 있는 경우

즉, (i * j)이나 (j * i)이나 같은 직사각형으로 본다는 것입니다. 그러면 중복체크를 해야합니다.

 

그러면

높이가 1일 때 가능한 너비 => 1, 2, 3, 4, 5, 6

높이가 2일 때 가능한 너비 => 2, 3

답 8

 

이렇게 축소를 시킬 수 있습니다.

여기서 찾은 규칙성이 높이는 1부터 sqrt(N)까지, 너비는 i부터 i * j <= N까지임을 알 수 있습니다.

 

 

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
#include <iostream>
#include <cmath>
using namespace std;
 
int N;
 
void func() {
    int ans = 0;
    for (int i = 1; i <= sqrt(N); i++) {
        for (int j = i; i * j <= N; j++) {
            ans++;
        }
    }
 
    cout << ans << '\n';
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N;
    func();
 
    return 0;
}
 cs

 

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

boj 16719 ZOAC  (0) 2021.03.15
boj 3085 사탕 게임  (0) 2021.02.26
boj 3985 롤 케이크  (0) 2021.02.25
boj 2116 주사위 쌓기  (0) 2021.02.25
boj 10163 색종이  (0) 2021.02.24

+ Recent posts

티스토리툴바