Post

BOJ_23351_물주기 (Java, C++)

Posted
Preview Image
By Hyeon Jae Kim
11 min read
BOJ_23351_물주기 (Java, C++)

[Silver III] 물 주기 - 23351

문제 링크

성능 요약

메모리: 14312 KB, 시간: 128 ms

분류

그리디 알고리즘, 구현, 시뮬레이션

제출 일자

2025년 1월 26일 08:35:59

문제 설명

랑이 집사는 고양이들이 좋아한다는 캣닢을 직접 재배하려고 한다.

랑이 집사는 고양이들이 좋아한다는 캣닢을 직접 재배하려고 한다.

일직선으로 놓여진 $N$개의 화분에 캣닢이 하나씩 심어져 있다.

각 화분은 초기에 $K$만큼의 수분을 머금고 있고, 매일 아래와 같은 일이 순서대로 일어난다.

랑이 집사가 연속된 $A$개의 화분에 물을 준다. 이 때 물을 준 화분의 수분은 $B$만큼씩 증가한다. 모든 화분의 수분이 1씩 감소한다. 수분이 0이 된 화분에 있는 캣닢은 죽는다. 모든 캣닢이 살아 있는 기간이 최대한 길어지도록 물을 줄 때, 첫 캣닢이 죽는 날짜를 출력하는 프로그램을 작성하시오. 첫 날은 1일이다.

입력

첫째 줄에 자연수 $N$, $K$, $A$, $B$가 공백을 사이에 두고 주어진다. ($2 \le N \le 100$, $1 \le K \le 100$, $1 \le A \times B < N$, $A$는 $N$의 약수)

출력

모든 캣닢이 살아 있는 기간이 최대한 길어지도록 물을 줄 때, 첫 캣닢이 죽는 날짜를 출력한다.

문제 풀이

제한 조건이 100이기때문에 단순 구현으로 풀 수 있다. 하지만 세그먼트트리를 연습하고싶었다. 그래서 두가지 버전을 사용해보았다.

이 문제의 경우 단순히 최소 구간합을 구하는 것 뿐만 아니라 전체 구간에 -1을 뒤늦게 적용해야하는 Lazy Propagation 까지 사용해야한다.

코드

Java 코드

  1. 단순 구현 ```java /**
    • Author: nowalex322, Kim HyeonJae */

import java.io.; import java.util.;

public class Main { static BufferedReader br; static BufferedWriter bw; static StringTokenizer st; static int N, K, A, B, arr[], res; public static void main(String[] args) throws Exception { new Main().solution(); }

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

public void solution() throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in)); //        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_23351_물주기/input.txt")));
    bw = new BufferedWriter(new OutputStreamWriter(System.out));
    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    A = Integer.parseInt(st.nextToken());
    B = Integer.parseInt(st.nextToken());

    arr = new int[N];
    Arrays.fill(arr, K);
    boolean flag = false;
    while(!flag){
        res++;

        int startIdx = findMinSet();
        waterPlants(startIdx);
        flag = checkEnd();
    }
    
    bw.write(String.valueOf(res));
    bw.flush();
    bw.close();
    br.close();
}

private int findMinSet() {
    int idx = -1;
    int sum = Integer.MAX_VALUE;
    for (int i = 0; i <= N-A; i++) {
        int tmp = 0;
        for (int j = i; j < i+A; j++) {
            tmp += arr[j];
        }
        if(tmp < sum){
            sum = tmp;
            idx = i;
        }
    }
    return idx;
}

private void waterPlants(int startIdx) {
    for(int i = startIdx; i < startIdx + A; i++){
        arr[i] += B;
    }
}

private boolean checkEnd() {
    for(int i = 0; i < N; i++){
        arr[i]--;
        if(arr[i] <= 0) return true;
    }
    return false;
} } ```
  1. 세그먼트 트리 + Lazy Propagation ```java // 세그먼트트리 + lazy propagation 풀이

/**

  • Author: nowalex322, Kim HyeonJae */

import java.io.; import java.util.;

public class Main { static BufferedReader br; static BufferedWriter bw; static StringTokenizer st; static int N, K, A, B, arr[], res; static int[] tree; static long[] lazy; public static void main(String[] args) throws Exception { new Main().solution(); }

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

public void solution() throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in)); //        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_23351_물주기/input.txt")));
    bw = new BufferedWriter(new OutputStreamWriter(System.out));

    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    A = Integer.parseInt(st.nextToken());
    B = Integer.parseInt(st.nextToken());

    arr = new int[N];
    Arrays.fill(arr, K);
    boolean flag = false;

    int h = (int) Math.ceil(Math.log(N) / Math.log(2));
    int size = (1 << (h+1));

    tree = new int[size];
    lazy = new long[size];

    init(1, 0, N-1);
    
    while(!flag){
        res++;

        // 최소구간찾기
        int minSum = Integer.MAX_VALUE;
        int minIdx = 0;
        for(int i=0; i<N-A+1; i++){
            int sum = query(1, 0, N-1, i, i+A-1);
            if(sum < minSum){
                minSum = sum;
                minIdx = i;
            }
        }
        update(1, 0, N-1, minIdx, minIdx+A-1, B);

        update(1, 0, N-1, 0, N-1, -1);

        int minValue = query(1, 0, N-1, 0, 0);
        for(int i=1; i<N; i++) {
            minValue = Math.min(minValue, query(1, 0, N-1, i, i));
        }
        if(minValue <= 0) flag = true;
    }

    bw.write(String.valueOf(res));

    bw.flush();
    bw.close();
    br.close();
}

// segment tree 초기화
private int init(int node, int start, int end){
    if(start == end) return tree[node] = arr[start];

    int mid = start + (end - start)/2;
    return tree[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid+1, end);
}

// lazy propagation. 원리는 특정 지연값을 특정구간에 포함되는 노드에 전파해두고
// 그 구간 조회/업데이트 쿼리 있으면 그때 구간길이만큼 곱해서 반영, 그 외에는 반영안함.
private void propagate(int node, int start, int end){
    if(lazy[node] != 0) { // 지연된 업데이트가 있다면
        tree[node] += (end-start+1) * lazy[node]; // 현재 구간(end-start+1)에 지연된 값을 적용

        if(start != end) { // 리프노드 아니면 자식있으므로 자식에게 전파
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}

// 구간합조회
private int query(int node, int start, int end, int left, int right){
    propagate(node, start, end);
    if(start > right || end < left) return 0;
    if(start >= left && end <= right) return tree[node];

    int mid = start + (end - start)/2;
    return query(node*2, start, mid, left, right) + query(node*2 + 1, mid+1, end, left, right);
}

// 구간업데이트
private void update(int node, int start, int end, int left, int right, int value){
    propagate(node, start, end);

    if(start > right || end < left) return;
    if(start >= left && end <= right) {
        tree[node] += (end - start + 1) * value;
        if(start != end) {
            lazy[node * 2] += value;
            lazy[node * 2 + 1] += value;
        }
        return;
    }

    int mid = start + (end - start)/2;
    update(node*2, start, mid, left, right, value);
    update(node*2 + 1, mid+1, end, left, right, value);
    tree[node] = tree[node*2] + tree[node*2 + 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
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

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int N, K, A, B;
vector<int> tree, lazy;

void propagate(int node, int start, int end) {
    if (lazy[node]) {
        tree[node] += (end - start + 1) * lazy[node];
    }

    if (start != end) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

int init(vector<int>& arr, int node, int start, int end) {
    if (start == end) return tree[node] = arr[start];
    int mid = start + (end - start) / 2;
    return tree[node] = init(arr, node * 2, start, mid) +
                        init(arr, node * 2 + 1, mid + 1, end);
}

int query(int node, int start, int end, int left, int right) {
    propagate(node, start, end);
    if (start > right || end < left) return 0;
    if (start >= left && end <= right) return tree[node];

    int mid = start + (end - start) / 2;

    return query(node * 2, start, mid, left, right) +
           query(node * 2 + 1, mid + 1, end, left, right);
}

void update(int node, int start, int end, int left, int right, int value) {
    propagate(node, start, end);
    if (start > right || end < left) return;
    if (start >= left && end <= right) {
        tree[node] += (end - start + 1) * value;
        if (start != end) {
            lazy[node * 2] += value;
            lazy[node * 2 + 1] += value;
        }
        return;
    }
    int mid = start + (end - start) / 2;
    update(node * 2, start, mid, left, right, value);
    update(node * 2 + 1, mid + 1, end, left, right, value);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void solve() {
    cin >> N >> K >> A >> B;
    vector<int> arr(N, K);

    int h = ceil(log2(N));
    int size = (1 << (h + 1));
    tree.resize(size);
    lazy.resize(size);

    init(arr, 1, 0, N - 1);

    int res = 0;
    while (true) {
        res++;

        int minSum = INT_MAX, minIdx = 0;
        for (int i = 0; i <= N - A; i++) {
            int sum = query(1, 0, N - 1, i, i + A - 1);
            if (sum < minSum) {
                minSum = sum;
                minIdx = i;
            }
        }

        update(1, 0, N - 1, minIdx, minIdx + A - 1, B);
        update(1, 0, N - 1, 0, N - 1, -1);

        int minValue = query(1, 0, N - 1, 0, 0);
        for (int i = 1; i < N; i++) {
            minValue = min(minValue, query(1, 0, N - 1, i, i));
        }

        if (minValue <= 0) break;
    }

    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}
알고리즘
C++ Java 백준 알고리즘
This post is licensed under CC BY 4.0 by the author.