[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. 단순 구현

/**
 * 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();
    }

    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;
    }
}

2. 세그먼트 트리 + Lazy Propagation

// 세그먼트트리 + 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();
    }

    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++ 코드

/**
 * 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;
}