[BOJ] 31066번 - 비 오는 날 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

2023.12.30일에 처음으로 SciOI 2023 Open Contest · Arena #16 에 참가했다.

코딩테스트를 본다는 생각으로 긴장감을 가지고 시작했다. 이 문제가 첫 문제였다.

당시에 너무 복잡하게 생각했는지 꼬여버렸던 문제를 오늘 다시 정리해서 풀어보았다.

풀이 과정에서 2가지 문제를 알게되어 이를 정리하려고 한다.

1. 틀린 예외처리

if(m == 1 && k == 1) return -1;

 

처음에는 위와 같이 우산이 1개이고 우산을 쓸 수 있는 사람 수가 1명일 경우에는 무조건 불가능하다고 했다.

하지만 만약에 사람이 건너야 하는 사람이 1명이면 이 경우에도 불가능할까?

내가 생각하지 못했던 부분 첫번째였다. 사람이 1명일 경우에는 1회로 가능하다는 것을 빼먹었었다.

if(m == 1 && k == 1) {
    if(n == 1) return 1; //사람이 1명이면 1번으로 가능
    return -1;
}

2. 복잡한 생각

늘 긴장하고 문제를 풀 때마다 평소보다 문제를 어렵게 생각한다고 느낀다.

이 문제에서도 설명이 친절하게 되어있어 구현을 차근차근해보면 풀렸을 것 같다.

하지만 당시에 수식으로 풀어야 한다는 생각을 계속 하면서 틀린 점을 찾아가려고 했다. 아래는 틀린 풀이이다.

n % (m*k-1) == 0 ? n / (m*k-1) : n / (m*k-1) + 1

 

이 문제를 딱 보자마자 생각난 알고리즘은 Greedy이다.

한번 이동할 때 모든 우산을 사용하여 이동하고 1명이 모든 우산을 들고 돌아와야지 최소 이동횟수를 구할 수 있기 때문이다.

이대로 올바르게 구현했다면 맞을 것이다.

 

하지만 위와 같이 생각하면서 m*k명이 갔다가 1명이 돌아오면 된다는 생각에 m*k-1 을 가지고 수식을 작성하려 했다.

반례는 n번보다 더 많은 횟수를 왔다갔다 할 수 있는 경우가 존재하는데 위의 풀이는 n번 이하만을 구할 수 있다.

반례 - 올바른 정답

 

위와 같은 입력이 주어진다면 수식 풀이는 5회라는 잘못된 답을 도출할 것이다.

그래서 아래와 같이 설명대로 구현해보았다.

int count = 0;
int start = n;
int s = m;
int end = 0;
int e = 0;

while(end < n) {
    if(s != 0) {
        int t = s * k;
        start -= t;
        end += t;
        e += s;
        s = 0;
    }
    else {
        start += 1;
        end -= 1;
        s = e;
        e = 0;
    }
    count++;
}

 

아마 실제 돌아가는 방식대로 구현해보려 하지 않았다면 반례를 생각하기 쉽지 않았을 것 같다.

머리를 식히고 다시 생각해보니 정말 단순한 문제였지만 깨달은 점이 있다.

 

늘 시간에 쫓겨 빠르게 풀려고 하느라 시야가 좁아지고 있었다.

만약 풀릴 것 같은데 고치면 고칠수록 꼬여가는 느낌이 들면 급하게 생각하지 말고 보이는 그대로 구현해보며 동작 방식을 이해하고 그 다음에 이를 개선해 나가는 방법을 적용할 수 있도록 마음의 여유를 가져야겠다.

---

🍀 풀이 🍀

package SciOI2023;

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

public class A1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            bw.write(solve(n, m, k) + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static int solve(int n, int m, int k) {
        if(m == 1 && k == 1) { //우산이 1개이고 1명만 쓸 수 있다면
            if(n == 1) return 1; //사람이 1명이면 1번으로 가능
            return -1; //그 외에는 불가능
        }

        int count = 0;
        boolean umbrella = true; //우산이 창의 인재관에 있는지
        int destination = 0; //융합인재관에 있는 학생 수

        while(destination < n) {
            if(umbrella) {
                destination += m * k;
                umbrella = false;
            }
            else {
                destination -= 1;
                umbrella = true;
            }
            count++;
        }
        return count;
    }
}