https://www.acmicpc.net/problem/20444 👈 문제 확인
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.1 초 | 1024 MB | 277 | 108 | 93 | 40.969% |
문제
오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!
색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!
색종이를 자를 때는 다음과 같은 규칙을 따른다.
- 색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
- 자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
- 이미 자른 곳을 또 자를 수 없다.
분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.
궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.
입력
첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)
출력
첫 줄에 정확히 n번의 가위질로 k개의 색종이 조각을 만들 수 있다면 YES, 아니라면 NO를 출력한다.
문제풀이
이분탐색을 통해 해결할 수 있다.
위 그림에서 확인할 수 있듯이
가로로 자른 횟수를 x
세로로 자른 횟수를 y 라고 한다면
총 조각의 개수는 (x+1)*(y+1)로 자명하다.
따라서 (x+1)*(y+1) = K 식이 성립 되는지 검사해야 한다.
이분탐색을 진행하기 위해 비교할 mid의 값을 x라고 하면, y는 N-x가 되고
x(가로 횟수)를 가지고 0번부터 N//2 까지 검사하면 된다.
왜 N까지 검사하지않고?
-> 총 횟수가 정해져 있기 때문에 가로+세로가 일정하다.
-> 가로랑 세로의 결과가 같으므로 (가로, 세로)횟수가 대칭일 경우 같은 조각개수가 나온다
ex) 가로1+세로9 = 가로9+세로1그럼 mid의 값이 커지는 경우, 작아지는 경우는 어떻게 처리할까?
-> mid가 N//2에 가까울 수록 값이 커진다.
-> 합이 일정한 두 양의정수의 곱은 두수의 차이가 적을 수록 커진다. (산술기하평균...)
Python3 코드
import sys
N, K = map(int, sys.stdin.readline().split())
def binarySearch(left, right):
while left <= right:
mid = (left + right) // 2 # mid는 가로로 자른 횟수
value = (mid+1) * ((N-mid)+1) # value는 조각의 개수
if value > K:
right = mid - 1
elif value < K:
left = mid + 1
else:
print('YES')
return
print('NO')
return
binarySearch(0, N//2)회고
이분탐색 알고리즘이 부족해서 요즘에 많이 풀고 있는데, 문제를 풀때마다 헷갈리는 부분이 많다.
특히 등호를 포함하냐 안하냐의 판단이 제일 까다롭고, 틀려도 디버깅하기가 쉽지 않다...
