[BOJ] 백준 20444: 색종이와 가위 - Python

문제

---

 https://www.acmicpc.net/problem/20444

20444번: 색종이와 가위

 

풀이

---

가위질을 가로로 자른 횟수(rowCut)와 세로로 자른 횟수(colCut)로 나눠보면 (즉, n = rowCut + colCut)

조각의 개수는 (rowCut + 1) * (colCut + 1) 만큼 나옵니다.

 

따라서 rowCut이 정해지면 조각의 개수가 정해집니다.

 

또한,, 

1. 조각의 개수는 rowCut 과 colCut 개수에 대해 대칭적?이기 때문에 rowCut을 0 ~ n 까지 확인할 필요 없이 0 ~ n // 2 까지만 확인하면 됩니다.

2. rowCut을 0 ~ n // 2 까지 늘려보는 과정에서 조각의 개수는 계속하여 늘어나게 됩니다. rowCut과 colCut의 차이가 작아질수록 조각의 개수가 늘어나기 때문입니다.

 

위에 언급한 2번 조건과 입력의 크기, 시간제한 등을 고려하면 rowCut을 선형적으로 늘려가는 것이 아닌 이분탐색을 생각해 볼 수 있습니다.

 

따라서 rowCut을 범위 내에서 줄이고 늘리고를 반복해가며 조각의 개수가 target value인 k에 도달할 수 있는지를 체크하면 문제를 해결할 수 있습니다.

n, k = map(int, input().split())
left = 0
right = n // 2
isPossible = False

while left <= right:
    rowCut = (left + right) // 2
    colCut = n - rowCut
    # 가로, 세로 각각 rowCut, colCut번씩 잘랐다면 (rowCut + 1) * (colCut + 1) 조각이 생김
    pieces = (rowCut + 1) * (colCut + 1)
    if k == pieces:
        print('YES')
        isPossible = True
        break
    if k > pieces:
        left = rowCut + 1
    else:
        right = rowCut - 1

if not isPossible:
    print('NO')