[BaekJoon] 35307번 - 하얀 전파 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 격자에 대해 초기엔 모든 칸이 검은색이며 특정 위치를 흰색으로 바꾼 후 전파를 시작해서 전파가 끝났을 때 하얀 칸의 최대 갯수와 해당 시간을 구하는 문제로 격자의 크기가 매우 커서 직접 전파를 하는 방식은 어렵다. 특정 칸을 하얀색으로 바꿨을 때 가로 또는 세로 방향으로 전파가 멈추는데 걸리는 시간을 몫과 나머지를 활용하면 구할 수 있는데 가로 방향은 가로의 길이를 좌우 방향 각각의 1초당 진행 크기로 나눈 몫으로 구할 수 있다. 이때 나머지가 존재하면 1초가 더 걸리며 가로 방향 진행이 없는 경우 전파가 멈추는데 걸리는 시간은 0이다. 세로 방향 역시 마찬가지이며 이를 통해 가로 방향 전체로 전파되는데 걸리는 최소 시간과 세로 방향 전체로 전파되는데 걸리는 최소 시간을 구할 수 있다. 채울 수 있는 하얀 칸의 수는 각 시간이 0이면 해당 방향으로는 채울 수 없지만 0이 아니면 언젠가는 채우므로 이를 통해 구할 수 있다. 전파 시간의 경우 가로 전파 시간이 더 짧으면 가로 방향 전파가 끝난 후 끝 위치에서 세로 방향 전파를 시작하고, 세로 방향 전파 시간이 더 짧으면 반대이므로 가로 방향 전파 시간과 세로 방향 전파 시간의 합이 전체 전파가 끝나는데 걸리는 최소 시간이다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            long n = Long.parseLong(st.nextToken());
            long m = Long.parseLong(st.nextToken());
            long l = Long.parseLong(st.nextToken());
            long r = Long.parseLong(st.nextToken());
            long u = Long.parseLong(st.nextToken());
            long d = Long.parseLong(st.nextToken());

            long ht = (u + d == 0) ? 0 : (n - 1 + u + d - 1) / (u + d);
            long wt = (l + r == 0) ? 0 : (m - 1 + l + r - 1) / (l + r);

            long fill = 1;
            if (ht != 0) fill *= n;
            if (wt != 0) fill *= m;

            sb.append(fill).append(" ").append(ht + wt).append("\n");
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

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

    int t;
    cin >> t;

    while (t--) {
        long long n, m, l, r, u, d;
        cin >> n >> m >> l >> r >> u >> d;

        long long ht = (u + d == 0) ? 0 : (n - 1 + u + d - 1) / (u + d);
        long long wt = (l + r == 0) ? 0 : (m - 1 + l + r - 1) / (l + r);

        long long fill = 1;
        if (ht != 0) fill *= n;
        if (wt != 0) fill *= m;

        cout << fill << ' ' << ht + wt << '\n';
    }
}

---