(Python/🥇5)백준알고리즘 20444번: 색종이와 가위

 

문제 바로가기 

색종이와 가위

 

문제:

오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!! 색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!! 색종이를 자를 때는 다음과 같은 규칙을 따른다.

• 색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
• 자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
• 이미 자른 곳을 또 자를 수 없다.

분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다. 궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.

입력:

첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)

출력:

첫 줄에 정확히 n번의 가위질로 k개의 색종이 조각을 만들 수 있다면 YES, 아니라면 NO를 출력한다.

 

풀이:

 

 

시도 1 : 틀린코드

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, m = map(int,input().split())

while n > 0:
    if m %2 :
        m -= 1
    else:
        m = m //2
    if m < 1 or (m == 1 and n > 0):
        print("NO")
        exit()
    n -= 1
print("YES" if m == 1 else "NO")

시간을 0.1초 주어진다.  n, k 의 숫자가 2^31, 2^63 이다...

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, m = map(int,input().split())

left = 0 ; right = n // 2
while left <= right:
    x = (left + right) // 2
    y = n - x
    answer= (x+1) * (y+1)
    # 1, 3
    if answer == m :
        print("YES")
        exit()
    #조각이 더 많음
    if answer < m:
        left = x + 1
    else:
        right = x - 1
print("NO")

 

이분탐색을 사용했다. right = n//2 인 이유는  대칭성을 띄기 때문에 n까지 안 해도 된다.

answer 는 색종이갯수 구하는 공식이다.

2번씩 자르면 총 9 개가 나온다.

 

₩