[Python][SWEA] 14178. 1차원 정원 D3

SW Expert Academy

---

🗒️ 파이썬 코드 풀이

T = int(input())
for test_case in range(1, T + 1):
    N,D = map(int,input().split())
    min_bunmugi = N // (2*D+1)
    if N % (2*D+1) == 0 :
       print(f"#{test_case} {min_bunmugi}")
    else:
        print(f"#{test_case} {min_bunmugi+1}")

 

1. 문제에 수직 정원이라 되어있는데, 수평으로 해도 큰 문제가 없다.

 

2. 여기에서 가장 최적의 순간은 분무기가 겹치지 않고 딱 1개씩 맞는 것이다. 

이것을 가정하고 문제를 풀면 쉽게 풀 수 있다.

(만일, 딱 겹치지 않는다고 해도, 최적의 배치를 하고 +1만 해주면 된다.)

 

3. 딱 맞아 떨어지는  경우는 % (나누기) 연산을 했을때 0이 될 것이고,

그렇지 않은 경우 0이 아닌 값이 나올 것이다. (이런 경우 +1 )

 

🧐 문제 코멘트

문제 처음에는 완전탐색을 할까 하다가, 100인 경우 100!의 시간 복잡도가 될 것 같아서 포기했다.

문제 예시보다 좀 더 큰 정원을 만들어 생각을 했는데, 많은 것을 생각 할 필요없이 최적의 순간을 찾고,

모자르면 +1만 해주면 되겠다는 생각했다. (정원의 꽃은 순서가 없고, 분무기 또한 순서 신경 안씀)

역시 손으로 하나하나 구현해보면, 어떤식으로 설계할지 감이 잡히는 것 같다.

---

📚 문제

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

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

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