[BOJ/백준] 9349번 : Fegla and the Bed Bugs (Java)

📘 백준 9349번 : Fegla and the Bed Bugs

---

문제 바로가기

🔤 문제 번역

문제

Fegla(일명 mmaw)는 여러 팀을 코치하고 있다. 이 팀들은 모두 한 장소에서 함께 훈련하지만, 불행히도 그 장소는 환기가 좋지 않고 팀 수에 비해 매우 좁다. 이러한 환경 때문에 이상한 생물이 나타났는데, 그것은 바로 침대벌레(The Bed Bug)이다.

이들은 기생 곤충으로, 사람을 물어 피를 빨아 먹는다. 이상하게도 Fegla를 혼란스럽게 한 점은 일부 팀원들은 전혀 물리지 않았다는 것이다. 하지만 그는 무엇보다도 이 벌레들을 없애는 데 관심이 있었다. 벌레들의 행동을 한동안 관찰한 결과, 서로 아주 가까이 있을 때 번식한다는 사실을 알게 되었다.

따라서 Fegla는 당신의 도움이 필요하다. 빈 칸이 일렬로 N개 있는 직선과 벌레의 수 K가 주어질 때, 벌레들을 배치하여 인접한 두 벌레 사이의 빈 칸 수의 최소값을 최대화하는 최적의 배치를 구하라.

예를 들어, N = 4, K = 2인 경우 최적의 배치는 다음과 같으며, 이때의 정답은 2이다.

벌레 / 빈 칸 / 빈 칸 / 벌레

입력

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이후 T개의 줄에 걸쳐 각 줄마다 두 정수 N, K가 주어진다.

• 2 ≤ N ≤ 200
• 2 ≤ K ≤ N

출력

각 테스트 케이스마다 한 줄에 하나씩, 최적의 배치에서 인접한 두 벌레 사이의 최소 거리(빈 칸 수)를 출력하라.

💡 문제 풀이

---

직선에 벌레를 최대한 떨어뜨려 놓았을 때 빈칸의 최댓값을 찾는 문제.

마지막 칸에 벌레를 둔 후 남은 칸을 벌레의 수로 고르게 나누었다고 했을 때,

나누어 떨어지든 안 떨어지든 나눈 몫이 (벌레 하나 + 다음 벌레까지 빈칸 최솟값)이 되므로 그 값에서 1을 뺀 값을 출력한다.

즉, (칸 수 - 1) / (벌레 - 1) - 1

✅ 코드 (Java)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/9349
public class B9349_Fegla_and_the_Bed_Bugs {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine()); // 테스트케이스
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			sb.append((N - 1) / (K - 1) - 1).append("\n");
		}
		System.out.println(sb);
		br.close();
	}
}

💾 제출 결과

---

보러 가기