백준 20444 : 색종이와 가위 (Python)

본문링크

N,K=map(int,input().split())

start=0 ; end=N
while start<=end:
    mid=(start+end)//2
    if (mid+1)*( (N-mid) +1 )>K:
        start=mid+1
    elif (mid+1)*( (N-mid) +1 ) <K:
        end=mid-1
    elif (mid+1)*( (N-mid) +1 ) == K:
        print("YES")
        exit(0)
print("NO")

📌 어떻게 접근할 것인가?

문제에서 정수 n, k 가 (1 ≤ n ≤ 2^31-1, 1 ≤ k ≤ 2^63-1) 이다.
이렇게 큰 범위를 완전탐색으로 풀기에는 시간이 너무 오래걸리기 때문에
이분탐색을 통해 접근해보았다.

먼저 가위질을 하면서 나오는 경우의 수를 직접 시뮬레이션 해서 구해보았다.
7번 가위질 - ( 8 , 14 , 18 , 20 ) 이 나오고
(7+1) x (0+1)=8
(6+1) x (1+1)=14
(5+1) x (2+1)=18
(4+1) x (3+1)=20
위와 같은 식이 나온다.

📌 어떻게 이분탐색할 것인가?

색종이로 나오는 경우의 수를 점화식으로 표현해보자면
1 부터 N//2 까지 (mid+1) x ( (N-mid)+1 ) 이 된다.

이때 mid 가 감소할수록 나오는 종이의 수는 감소한다.

따라서 start=0 end=N으로 잡은후 (mid+1) x ( (N-mid)+1 ) 값이 K 보다 크다면 start 를 증가시키고 작으면 end 를 감소시킨다.
이렇게 K 와 값이 같을때까지 이분탐색을 한다.

그리디와 시뮬레이션 , 이분탐색을 섞은 느낌이다.