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

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

20444번: 색종이와 가위

1. 색종이를 자를 때 한 변에 평행하게 자른다는 말은

     -> 가로 또는 세로 방향으로만 자를 수 있다는 뜻

   따라서 색종이를 n번 자르는 것은 가로방향 x번, 세로방향 n-x번으로 자를 수 밖에 없다. (0 <= x <= n)

 

2. 즉, n번 자를때 나올 수 있는 색종이 조각의 경우의 수는 

   (0+1) * (n+1)

   (1+1) * (n-1+1)

   (2+1) * (n-2+1)

    .

    .

    .

   (n-2+1) * (2+1)

   (n-1+1) * (1+1)

   (n+1) * (0+1)                              // 총 (n+1)가지이다.

 

   # 그런데, 첫번째와 마지막경우, 두번째와 마지막에서 두번째경우가 같고 이런식으로 중간값을 기준으로

      대칭되는 값이 같으므로 실제로 (n//2 + 1)가지만 확인하면 된다.

 

3. 따라서, lo = 0, hi = n//2 + 1로 두고 이분탐색을 통해 mid값을 구한 다음, 색종이 조각의 갯수를

   f함수로 구해준다. 색종이 조각의 갯수는 2번공식을 통해 알 수 있듯이 (mid + 1) * (n - mid + 1)개이다.

 

4. 이분 탐색을 진행하면서, f(mid)값이 k와 같으면 "YES"를 출력하고 프로그램을 종료하고

     f(mid)가 k보다 크면, mid값을 줄이고 f(mid)가 k보다 작으면, mid값을 늘리는 식으로 코드를 짰다. 

 

5. while문을 벗어날때까지 "YES"가 출력되지않으면, "NO"를 출력한다.

 

import sys
input = sys.stdin.readline
n, k = map(int,input().split())

def f(x):
    return (x + 1) * (n - x + 1)

lo, hi = 0, n // 2 + 1
while lo != hi:
    mid = (lo + hi) >> 1
    if f(mid) == k:
        print("YES")
        sys.exit(0)
    if f(mid) > k:
        hi = mid
    else:
        lo = mid + 1

print("NO")

(solved.ac 티어: 골드 5)

 

# 처음에 반대로 생각해 k값을 소인수분해 한 뒤, 소인수에 n이 있는지 없는 지 찾으려고 했다.

      -> 시간복잡도가 루트k인데, k**(1/2) <= 2**32이므로 시간초과가 날 것이라 예상했다.

 

# 두번째는, 2번과정에서 나온 식 (N+1)개를 배열arr에 넣고, 'k in arr' 이런식으로 in함수를 통해

   k가 arr에 존재하는지 판단하려고 했다.

      -> 모든 색종이 조각의 갯수 (N+1)개를 넣을 배열칸 N+1개가 필요하고, in함수는 O(N)이므로

          공간복잡도와 시간복잡도 모두 2**31이 되어 시간초과가 날 것이라 예상했다.

 

# n과 k가 둘다 너무 크므로, 이분탐색을 사용하기로 했다.

  이 과정에서 N+1가지 중 N//2+1가지만 확인해도 된다는 것을 깨달았고, 3번과정에서 사용한

  일반식을 도출할 수 있었다. 따라서 (가로로 자르는 횟수) 또는 (세로로 자르는 횟수)를 

  이분 탐색을 통해 구한 다음 f함수에 넣어 색종이 조각의 수를 구한 다음 그 값과 k값을

  비교해 lo, hi값을 갱신하는 식으로 코드를 짰다.

 

# f(mid)값이 k보다 클때 lo갱신, hi갱신 / k보다 작을때 lo갱신, hi갱신 등 여러가지 세세한 경우의

   수가 존재해 "틀렸습니다"를 많이 받았다. 다음부턴 좀 더 꼼꼼하게 체크해야겠다.