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

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표

www.acmicpc.net

2636번과 매우 유사한 문제입니다.

2636번과 다른점은 적어도 2변 이상이 공기와 인접해야 치즈가 녹는다는 점입니다.

가장자리에는 치즈가 없기때문에 0,0에서 bfs로 공기부분을 체크하고

반복문으로 치즈가 공기와 인접하는지 확인하고 2변 이상이 인접하면 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
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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int list[100][100], N, M;
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
bool visit[100][100];
 
void bfs() {
    memset(visit, false, sizeof(visit));
 
    queue<pair<int, int> > q;
    q.push({ 0,0 });
    visit[0][0] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = 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 >= M) continue;
            if (visit[nx][ny] || list[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!list[i][j]) continue;
 
            int cnt = 0;
            for (int x = 0; x < 4; x++) {
                int ni = i + direct[x][0];
                int nj = j + direct[x][1];
 
                if (visit[ni][nj]) cnt++;
            }
 
            if (cnt >= 2) list[i][j] = 0;
        }
    }
}
 
bool chk() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (list[i][j]) return true;
        }
    }
 
    return false;
}
 
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();
    for (int ans = 1; ; ans++) {
        bfs();
        func();
        if (!chk()) {
            cout << ans << '\n';
            break;
        }
    }
 
    return 0;
}
cs

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

boj 16956 늑대와 양  (0) 2021.02.03
boj 20419 화살표 미로 (Easy)  (0) 2021.01.23
boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 1039 교환  (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/2636

 

2636번: 치즈

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진

www.acmicpc.net

판의 가장자리에는 치즈가 없기 때문에 0,0에서 bfs로 탐색하여 공기 부분을 체크를 합니다.

그 후에 반복문으로 치즈가 있는 위치에 인접한 좌표에 공기가 있으면 0으로 바꿔줍니다.

이 과정을 반복하여 치즈가 모두 녹아 없어지는 데 걸린 시간을 구하면서 1시간 전에 남아있는 치즈조각의 갯수를 출력합니다.

(치즈를 한번 녹였을 때 남아있는 치즈조각의 갯수를 계속해서 갱신합니다.)

 

 

[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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int list[100][100], N, M, pre, ans;
int direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
bool visit[100][100];
 
void bfs() {
    memset(visit, false, sizeof(visit));
    queue<pair<int, int> > q;
    q.push({ 0,0 });
    visit[0][0] = true;
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = 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 >= M) continue;
            if (list[nx][ny] || visit[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    ans = pre;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            if (!list[i][j]) continue;
 
            for (int k = 0; k < 4; k++) {
                int nx = i + direct[k][0];
                int ny = j + direct[k][1];
 
                if (visit[nx][ny]) {
                    list[i][j] = 0;
                    ans--;
                    break;
                }
            }
        }
    }
}
 
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]) pre++;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    if (!pre) cout << "0\n0\n";
    for (int T = 1; pre ; T++) {
        bfs();
        func();
        if (!ans) {
            cout << T << '\n' << pre << '\n';
            break;
        }
 
        pre = ans;
    }
 
    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
102
103
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
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][101];
    static boolean visit[][] = new boolean[101][101];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, cnt;
 
    static void removeCheese() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (list[i][j] == 1) {
                    boolean chk = false;
                    for (int d = 0; d < 4; d++) {
                        int nx = i + direct[d][0];
                        int ny = j + direct[d][1];
 
                        if (visit[nx][ny]) {
                            chk = true;
                            break;
                        }
                    }
 
                    if (chk) {
                        list[i][j] = 0;
                        cnt--;
                    }
                }
            }
        }
    }
 
    static void bfs() {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { 0, 0 });
        visit[0][0] = 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;
            }
        }
    }
 
    static void init() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(visit[i], false);
        }
    }
 
    static void func() {
        int pre = cnt;
        for (int t = 1;; t++) {
            bfs();
            removeCheese();
            init();
            if (cnt == 0) {
                System.out.println(t);
                System.out.println(pre);
                return;
            }
            pre = cnt;
        }
    }
 
    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] == 1)
                    cnt++;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 2638 치즈  (0) 2021.01.22
boj 17142 연구소 3  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22
boj 3055 탈출  (0) 2021.01.22
boj 2234 성곽  (0) 2021.01.22

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

 

11003번: 최솟값 찾기

N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

www.acmicpc.net

A[i-L+1]~A[i] 중 최솟값을 구하는 문제로 Deque를 이용하여 해결하였습니다.

 

큐가 비어있을 때는 바로 삽입하면 되고

반복문을 이용하여 삽입하려는 수가 큐의 뒤에있는 수보다 작을때마다 뒤의 값을 제거한 후에 삽입합니다.

 

만약 A[i-L+1]이 양수가 되면 큐의 앞에있는 수가 제거되었는지 확인하고 제거되지 않았으면 제거합니다.

그럼 큐의 맨앞에 있는 수가 최솟값이므로 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[], ans[];
    static int N, L;
 
    static void func() {
        Deque<Integer> dq = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            if (dq.isEmpty())
                dq.addLast(list[i]);
            else {
                while (true) {
                    if (dq.isEmpty())
                        break;
                    if (dq.peekLast() > list[i])
                        dq.removeLast();
                    else
                        break;
                }
 
                dq.addLast(list[i]);
            }
 
            if (L <= i) {
                if (dq.peek() == list[i - L])
                    dq.removeFirst();
            }
 
            ans[i] = dq.peek();
        }
    }
 
    static void print() {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < N; i++) {
            sb.append(ans[i] + " ");
        }
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
        ans = new int[N];
        L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}
cs

'algorithm > data-structure' 카테고리의 다른 글

boj 5639 이진 검색 트리  (0) 2021.01.24
boj 1991 트리 순회  (0) 2021.01.22
boj 1517 버블 소트  (0) 2021.01.22
boj 2517 달리기  (0) 2021.01.22
boj 3425 고스택  (0) 2021.01.22

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

 

1517번: 버블 소트

첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다.

www.acmicpc.net

문제는 버블 소트이지만 머지 소트를 이용하여 해결할 수 있습니다.

머지 소트 과정에서 뒤에있는 인덱스가 앞으로 올 때 이동한 만큼 더해주면 됩니다.

 

 

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
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[], sorted[];
    static int N;
    static long ans;
 
    static void mergesort(int l, int m, int r) {
        int i = l;
        int k = l;
        int j = m + 1;
 
        while (i <= m && j <= r) {
            if (list[i] <= list[j]) {
                sorted[k] = list[i];
                i++;
            } else {
                if (list[k] != list[j])
                    ans += (j - k);
                sorted[k] = list[j];
                j++;
            }
            k++;
        }
 
        if (i > m) {
            for (; j <= r; j++, k++) {
                sorted[k] = list[j];
            }
        } else {
            for (; i <= m; i++, k++) {
                sorted[k] = list[i];
            }
        }
 
        for (int t = l; t <= r; t++) {
            list[t] = sorted[t];
        }
    }
 
    static void merge(int l, int r) {
        if (l != r) {
            int m = (l + r) / 2;
 
            merge(l, m);
            merge(m + 1, r);
            mergesort(l, m, r);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
        sorted = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        merge(0, N - 1);
        System.out.println(ans);
    }
}
cs

'algorithm > data-structure' 카테고리의 다른 글

boj 5639 이진 검색 트리  (0) 2021.01.24
boj 1991 트리 순회  (0) 2021.01.22
boj 11003 최솟값 찾기  (0) 2021.01.22
boj 2517 달리기  (0) 2021.01.22
boj 3425 고스택  (0) 2021.01.22

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

 

7453번: 합이 0인 네 정수

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

www.acmicpc.net

upperbound와 lowerbound를 연습하기 위해 풀었습니다..

 

emoney96.tistory.com/36

 

이 문제도 위의 문제와 같이 두 그룹으로 나눠서 이분탐색을 통해 값의 조합을 구하는 문제입니다.

 

먼저 list가 4개씩 주어지는데 크기가 4000이므로 2차원 배열을 이용하여 두 그룹으로 나눠줍니다.

 

그 다음 이분탐색으로 합이 0이되는 조합의 갯수를 upperbound-lowerbound로 찾아주면 되겠습니다.

 

 

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
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[][], N;
    static long sumlist[][], ans;
 
    static int upperbound(int l, int r, long x) {
        while (l < r) {
            int m = (l + r) / 2;
            if (sumlist[1][m] <= x)
                l = m + 1;
            else
                r = m;
        }
 
        return l;
    }
 
    static int lowerbound(int l, int r, long x) {
        while (l < r) {
            int m = (l + r) / 2;
            if (sumlist[1][m] < x)
                l = m + 1;
            else
                r = m;
        }
 
        return r;
    }
 
    static void binarysearch(int l, int r, long x) {
        if (l > r)
            return;
 
        int m = (l + r) / 2;
        if (sumlist[1][m] + x == 0) {
            ans += (upperbound(0, N * N, sumlist[1][m]) - lowerbound(0, N * N, sumlist[1][m]));
            return;
        } else if (sumlist[1][m] + x < 0)
            binarysearch(m + 1, r, x);
        else
            binarysearch(l, m - 1, x);
    }
 
    static void func() {
        Arrays.sort(sumlist[1]);
        for (int i = 0; i < N * N; i++) {
            binarysearch(0, N * N - 1, sumlist[0][i]);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[4][N];
        sumlist = new long[2][N * N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[0][i] = Integer.parseInt(st.nextToken());
            list[1][i] = Integer.parseInt(st.nextToken());
            list[2][i] = Integer.parseInt(st.nextToken());
            list[3][i] = Integer.parseInt(st.nextToken());
        }
 
        for (int i = 0, k = 0; i < N; i++) {
            for (int j = 0; j < N; j++, k++) {
                sumlist[0][k] = list[0][i] + list[1][j];
                sumlist[1][k] = list[2][i] + list[3][j];
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        System.out.println(ans);
    }
}
 cs

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

boj 2295 세 수의 합  (0) 2022.06.28
boj 2110 공유기 설치  (0) 2021.04.13
boj 2143 두 배열의 합  (0) 2021.01.22
boj 2805 나무 자르기  (0) 2021.01.22
boj 1920 수 찾기  (0) 2021.01.22

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

 

2143번: 두 배열의 합

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다

www.acmicpc.net

A배열의 연속 합 + B배열의 연속 합의 조합을 찾는 문제입니다.

 

A와 B 배열 각각의 연속합을 모두 저장한 후 이분탐색으로 사용하였습니다.

 

Alist의 값과 더할 Blist의 값을 이분탐색으로 찾아야하는데 중복된 값이 들어있을 수 있으므로 upper bound와 lower bound를 이용해야합니다.

 

C++에는 upper_bound와 lower_bound가 지원되어 편리하지만 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
102
103
104
105
106
107
108
109
110
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int A[], B[], Adp[], Bdp[];
    static ArrayList<Long> Alist, Blist;
    static int N, M;
    static long T, ans;
 
    static void init() {
        Alist = new ArrayList<>();
        Blist = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j++) {
                Alist.add((long) (Adp[j] - Adp[i - 1]));
            }
        }
 
        for (int i = 1; i <= M; i++) {
            for (int j = i; j <= M; j++) {
                Blist.add((long) (Bdp[j] - Bdp[i - 1]));
            }
        }
 
        Collections.sort(Alist);
        Collections.sort(Blist);
    }
 
    static long upperbound(int l, int r, long x) {
        r++;
        while (l < r) {
            int m = (l + r) / 2;
            if (Blist.get(m) <= x)
                l = m + 1;
            else
                r = m;
        }
        return l;
    }
 
    static long lowerbound(int l, int r, long x) {
        r++;
        while (l < r) {
            int m = (l + r) / 2;
            if (Blist.get(m) < x)
                l = m + 1;
            else
                r = m;
        }
        return r;
    }
 
    static void binarysearch(int l, int r, long x) {
        if (l > r)
            return;
 
        int m = (l + r) / 2;
        long sum = x + Blist.get(m);
        if (sum == T) {
            ans += (upperbound(0, Blist.size() - 1, Blist.get(m)) - lowerbound(0, Blist.size() - 1, Blist.get(m)));
            return;
        } else if (sum > T)
            binarysearch(l, m - 1, x);
        else
            binarysearch(m + 1, r, x);
    }
 
    static void func() {
        for (int i = 0; i < Alist.size(); i++) {
            binarysearch(0, Blist.size() - 1, Alist.get(i));
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        A = new int[N + 1];
        Adp = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            Adp[i] = Adp[i - 1] + A[i];
        }
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        B = new int[M + 1];
        Bdp = new int[M + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            B[i] = Integer.parseInt(st.nextToken());
            Bdp[i] = Bdp[i - 1] + B[i];
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        init();
        func();
        System.out.println(ans);
    }
}
cs

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

boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2805 나무 자르기  (0) 2021.01.22
boj 1920 수 찾기  (0) 2021.01.22
boj 17124 두 개의 배열  (0) 2021.01.22

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

 

2096번: 내려가기

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

www.acmicpc.net

기본적인 dp로 해결가능한 문제입니다.

 

각 칸의 최대/최소는

dp(i,0)의 값은 dp(i-1, 0), dp(i-1, 1)의 최대/최소

dp(i,1)의 값은 dp(i-1, 0), dp(i-1, 1), dp(i-1, 2)의 최대/최소

dp(i,2)의 값은 dp(i-1, 1), dp(i-1, 2)의 최대/최소

에서 해당 칸의 값을 더한 값으로 계산할 수 있습니다.

 

하지만 이 문제는 C++로 해결할 경우에 메모리제한이 4MB, JAVA로 해결할 경우에 256MB이 걸려있습니다.

 

메모리 절약을 위해 슬라이딩 윈도우 기법을 이용하였습니다.

이 문제는 i번째 줄의 값들을 구하기 위해서는 i-1번째 줄의 값만 있으면 됩니다.

따라서 공간은 2*3의 크기만큼 있으면 되고, 인덱스는 0과 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
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 maxdp[][], mindp[][];
    static int N, t;
 
    static void print() {
        t = 1 - t;
        int maxans = Math.max(maxdp[t][0], Math.max(maxdp[t][1], maxdp[t][2]));
        int minans = Math.min(mindp[t][0], Math.min(mindp[t][1], mindp[t][2]));
 
        System.out.println(maxans + " " + minans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        maxdp = new int[2][3];
        mindp = new int[2][3];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            maxdp[t][0] = Math.max(maxdp[1 - t][0], maxdp[1 - t][1]) + a;
            maxdp[t][1] = Math.max(maxdp[1 - t][0], Math.max(maxdp[1 - t][1], maxdp[1 - t][2])) + b;
            maxdp[t][2] = Math.max(maxdp[1 - t][1], maxdp[1 - t][2]) + c;
 
            mindp[t][0] = Math.min(mindp[1 - t][0], mindp[1 - t][1]) + a;
            mindp[t][1] = Math.min(mindp[1 - t][0], Math.min(mindp[1 - t][1], mindp[1 - t][2])) + b;
            mindp[t][2] = Math.min(mindp[1 - t][1], mindp[1 - t][2]) + c;
 
            
            t = 1 - t;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        print();
    }
}
cs

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

boj 17528 Two Machines  (0) 2021.01.28
boj 9657 돌 게임 3  (0) 2021.01.27
boj 1103 게임  (0) 2021.01.22
boj 12852 1로 만들기 2  (0) 2021.01.22
boj 16195 1, 2, 3 더하기 9  (0) 2021.01.22

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

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

연속된 수들의 부분합이기 때문에 two pointer로 해결할 수 있습니다.

저는 two pointer와 dp를 사용하였습니다.

 

우선 dp에 연속합을 저장해놓고

l~r의 합이 S보다 작으면 r++

l~r의 합이 S보다 크거나 같으면 ans을 갱신하고 l++

이 과정을 반복하여 ans을 출력하였습니다.

 

예외처리로 모든 값을 더해도 S보다 작다면 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
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[], dp[];
    static int N, S, ans = 100000;
 
    static void func() {
        int l = 1;
        int r = 1;
 
        while (r <= N) {
            if (dp[r] - dp[l - 1] < S) {
                r++;
            } else {
                ans = Math.min(ans, r - l + 1);
                l++;
            }
        }
 
        if (ans == 100000)
            ans = 0;
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
        dp = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            dp[i] = dp[i - 1] + list[i];
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

'algorithm > Two-Pointer' 카테고리의 다른 글

boj 1253 좋다  (0) 2021.10.21
boj 9024 두 수의 합  (0) 2021.10.21
boj 17609 회문  (0) 2021.03.29
boj 2559 수열  (0) 2021.02.12
boj 2003 수들의 합 2  (0) 2021.01.22

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

 

2517번: 달리기

첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는

www.acmicpc.net

자신 앞에 있는 사람들 중 자신보다 실력이 더 낮은 사람이 몇 명인지 구하는 문제입니다.

이 문제는 두 가지 방법으로 해결하였습니다.

예전에 배운적 있었던 Merge Sort방법과 이 문제의 풀이방법으로 명시되어 있는 Segment Tree 방법으로 문제를 두번 풀어보았습니다.

 

먼저 Merge Sort 방법입니다.

평소의 Merge Sort를 사용했던 것처럼 i번과 j번을 서로 비교해가며 큰 값을 sorted[k]에 저장하는 방식입니다.

 

여기서 기존의 Merge Sort에 추가해야 할 것이 하나 있는데

i번은 앞의 인덱스, j번은 뒤의 인덱스 이므로 j번 인덱스의 값이 앞으로 이동하게 되면 그 차이만큼 rank에서 빼줍니다. (i번이 뒤로가는 것은 무시하셔도 됩니다.)

 

 

C++로 구현한 merge sort방식
JAVA로 구현한 merge sort방식

 

작년에 C++로 동일한 방식으로 해결하였으나 java에서는 TLE를 받았는데

아는 형님께서 StringBuilder라는 것을 알려주셨고, 출력 부분에 이것만 추가하니 AC를 받았습니다.

StringBuilder를 이제 자주 써야겠다는 생각이 드는군요 ㅎㅎ

오늘도 하나 배워갑니다..

 

 

[Merge Sort]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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[][], rank[], sorted[][];
 
    static int N;
 
    static void mergesort(int l, int m, int r) {
        int i = l;
        int k = l;
        int j = m + 1;
 
        while (i <= m && j <= r) {
            if (list[i][0] > list[j][0]) {
                sorted[k][0] = list[i][0];
                sorted[k][1] = list[i][1];
 
                i++;
                k++;
            } else {
                sorted[k][0] = list[j][0];
                sorted[k][1] = list[j][1];
 
                rank[list[j][1]] -= (j - k);
 
                j++;
                k++;
            }
        }
 
        if (i > m) {
            for (; j <= r; j++, k++) {
                sorted[k][0] = list[j][0];
                sorted[k][1] = list[j][1];
            }
        } else if (j > r) {
            for (; i <= m; i++, k++) {
                sorted[k][0] = list[i][0];
                sorted[k][1] = list[i][1];
            }
        }
 
        for (int t = l; t <= r; t++) {
            list[t][0] = sorted[t][0];
            list[t][1] = sorted[t][1];
        }
    }
 
    static void merge(int l, int r) {
        if (l != r) {
            int m = (l + r) / 2;
            merge(l, m);
            merge(m + 1, r);
            mergesort(l, m, r);
        }
    }
 
    static void print() {
        StringBuilder sb = new StringBuilder();
        
        for (int i = 1; i <= N; i++) {
            sb.append(rank[i]+"\n");
        }
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1][2];
        sorted = new int[N + 1][2];
        rank = new int[N + 1];
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = i;
            rank[i] = i;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        merge(1, N);
        print();
    }
}
 cs

 

다음은 Segment Tree 방식입니다.

이 방식은 구간 합을 구하는 방식으로 해결할 수 있습니다.

먼저 list 배열을 실력의 오름차순으로 정렬한 후, 순서대로 인덱스를 트리에 저장해주시면 됩니다.

 

실력 순으로 query 후 update를 진행하기 때문에 query로 트리를 탐색할 때는 모든 값들이 자신보다 실력이 낮은 값들입니다.

여기서 인덱스가 자신보다 앞에 있는 갯수만 찾으시면 됩니다..

 

merge sort방식으로 구현
segment tree방식으로 구현

문제에 명시되어있는 풀이방법은 Segment Tree인데 Merge Sort방식으로 풀이한게 더 빠른 시간이 나왔습니다.

제가 로직을 잘못 구현했을 수도 있지만 여러방식으로 시도해봐야겠습니다..

 

 

[Segment Tree]

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.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][], tree[], rank[];
    static int N;
 
    static int query(int node, int s, int e, int l, int r) {
        if (l <= s && e <= r)
            return tree[node];
        if (s > r || e < l)
            return 0;
 
        int m = (s + e) / 2;
        return query(node * 2, s, m, l, r) + query(node * 2 + 1, m + 1, e, l, r);
    }
 
    static void update(int node, int s, int e, int idx) {
        if (idx < s || idx > e)
            return;
 
        tree[node]++;
        int m = (s + e) / 2;
        if (s != e) {
            update(node * 2, s, m, idx);
            update(node * 2 + 1, m + 1, e, idx);
        }
    }
 
    static void func() {
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i <= N; i++) {
            int ans = query(1, 1, N, 1, list[i][1]);
 
            rank[list[i][1]] = list[i][1] - ans;
            update(1, 1, N, list[i][1]);
        }
 
        for (int i = 1; i <= N; i++) {
            sb.append(rank[i]+"\n");
        }
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1][2];
        rank = new int[N + 1];
        tree = new int[N * 4];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = i;
        }
 
        Arrays.sort(list, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] > b[0])
                    return 1;
                else
                    return -1;
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 5639 이진 검색 트리  (0) 2021.01.24
boj 1991 트리 순회  (0) 2021.01.22
boj 11003 최솟값 찾기  (0) 2021.01.22
boj 1517 버블 소트  (0) 2021.01.22
boj 3425 고스택  (0) 2021.01.22

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

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

잘려진 나무의 길이를 적어도 M으로 하기위한 높이의 최댓값을 구하는 문제입니다.

최적의 값을 구하는 문제이기때문에 이분탐색 중에서 파라매트릭 서치를 이용하여 해결할 수 있습니다.

 

높이를 1~list중 최대로 설정하여 파라매트릭 서치를 돌리고

잘려진 나무의 높이의 합이 M보다 작으면 l ~ m-1

잘려진 나무의 높이의 합이 M보다 크거나 같으면 m+1~r

로 높이를 재설정하여 구하면 됩니다.

 

최적의 값을 구해야하기 때문에 합이 M이라고 해서 바로 리턴해버리는 실수가 없어야합니다.

(합이 M이 나오지 않는 입력도 주어질 수 있습니다.)

 

 

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
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[];
    static int N, M, maxheight;
    static long ans = 0;
 
    static void binarysearch(long l, long r) {
        if (l > r)
            return;
 
        long m = (l + r) / 2;
        long sum = 0;
        for (int i = 1; i <= N; i++) {
            if (list[i] <= m)
                continue;
            sum += (list[i] - m);
        }
 
        if (sum >= M) {
            ans = Math.max(ans, m);
            binarysearch(m + 1, r);
        } else {
            binarysearch(l, m - 1);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            maxheight = Math.max(maxheight, list[i]);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        binarysearch(1, maxheight);
        System.out.println(ans);
    }
}
cs

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

boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22
boj 1920 수 찾기  (0) 2021.01.22
boj 17124 두 개의 배열  (0) 2021.01.22

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

 

2003번: 수들의 합 2

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

www.acmicpc.net

dp로 list의 연속 합을 구현하였고 two pointer로 인덱스를 조정해가며 M과 비교하였습니다.

l~r의 합이 M과 같으면 정답인 경우이므로 ans++

l~r의 합이 M보다 작으면 수를 더해야하므로 r++

l~r의 합이 M보다 크면 수를 빼야하므로 l++

이 과정을 반복하여 r이 list.length와 같아지면 중지하면 됩니다.

 

 

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
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[], dp[];
    static int N, M, ans;
 
    static void func() {
        int l = 1;
        int r = 1;
        while (r < list.length) {
            if (dp[r] - dp[l - 1] == M) {
                ans++;
                l++;
            } else if (dp[r] - dp[l - 1] > M) {
                l++;
            } else
                r++;
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
        dp = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            dp[i] = dp[i - 1] + list[i];
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

'algorithm > Two-Pointer' 카테고리의 다른 글

boj 1253 좋다  (0) 2021.10.21
boj 9024 두 수의 합  (0) 2021.10.21
boj 17609 회문  (0) 2021.03.29
boj 2559 수열  (0) 2021.02.12
boj 1806 부분합  (0) 2021.01.22

+ Recent posts

티스토리툴바