SW Expert Academy 14178_1차원 정원 문제풀이 in C++

2022년 11월 12일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

SWEA : 14178_1차원 정원

문제 요구사항

---

• 1차원 수직선 위에 정원이 있다. 모든 정수 1 ≤ i ≤ N 에 대해, 좌표 i에 꽃이 하나씩 심겨 있다.
• 즉, 좌표 1, 2, …, N에 총 N개의 꽃이 심겨 있다.
• 꽃에 물을 주기 위해 자동 분무기를 사용한다.
• 분무기는 정수 좌표에 놓을 수 있으며, 좌표 x에 분무기를 놓았을 경우 닫힌 구간 [x - D, x + D]에 심긴 모든 꽃들에 물을 줄 수 있다.
• N과 D가 주어질 때, 모든 꽃이 한 개 이상의 분무기에서 물을 받을 수 있도록 하기 위해 필요한 최소한의 분무기 수를 구하는 프로그램을 작성하라.

[입력]

• 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
• 각 테스트 케이스는 하나의 줄로 이루어진다.
• 각 줄에는 두 개의 정수 N과 D (1 ≤ N, D ≤ 100) 가 공백 하나를 사이로 두고 주어진다.

[출력]

• 각 테스트 케이스마다 모든 꽃이 한 개 이상의 분무기에서 물을 받을 수 있도록 하기 위해 필요한 최소한의 분무기 수를 출력한다.

접근 방법

---

• 정원에 물을 뿌릴 수 있는 범위는 D * 2에 해당 x 위치까지 + 1해서 D * 2 +1 이다.
• 정원의 크기 N을 해당 범위로 나눴을 때 나머지가 0이라면, 말끔하게 모든 꽃에 물을 줄 수 있고, 그렇지 않다면 한 개를 추가적으로 더 설치 해야 한다.

풀이 순서

---

1. TC를 입력받고, 해당 TC만큼 반복한다.
2. N과 D를 입력받고, range 변수에 D * 2 + 1을 하여, 물을 뿌릴 수 있는 범위를 구한다.
3. N을 range로 나눴을 때 나머지가 0이라면, 말끔하게 물을 줄 수 있고, 그렇지 않다면 한 개를 추가적으로 설치 해야 한다.
4. 이와 같은 작업 반복

소스코드

---

#include <iostream>

using namespace std;

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

	int TC;
	cin >> TC;

	for (int test_case = 1; test_case <= TC; test_case++) {
		int N, D;
		cin >> N >> D;

		int range = D * 2 + 1;

		if (N % range == 0) {
			cout << "#" << test_case << " " << N / range << "\n";
		}
		else {
			cout << "#" << test_case << " " << N / range + 1 << "\n";
		}
	}

	return 0;
}

문제 풀이 결과

---