[BaekJoon] 백준 20444번 색종이와 가위

[BaekJoon] 백준 20444번 색종이와 가위

 

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

 

내코드

 

처음으로 규칙을 찾아보았다. 6(n)번 가위질을 하는 것을 예시로 들었을 때 모든 경우의 수는 다음과 같다.

7(1X7, 가로0 세로6), 12(2X6, 가로1 세로5), 15(3X5, 가로2 세로4), 16(4X4, 가로3 세로 3)

즉, 가로로 자르는 횟수와 세로로 자르는 횟수에 의해 잘라진 색종이의 개수(k)가 정해진다.

여기서 색종이의 개수를 두 수의 곱으로 표현해 뒀는데 각각의 수를 a, b라고 하자.

 

이를 식으로 표현해보면

a + b = n + 2

a x b = k

이다.

 

문제에서 입력으로 n과 k는 주어지므로 위의 식을 만족하는 a와 b를 구하면 된다.

b = n + 2 - a 이므로

a x (n + 2 - a) = k 이고

a^2 - (n + 2)a + k = 0 이다.

 

a, b는 둘다 양수여야 하므로

근의 공식을 이용하면

((n + 2) +- 루트((n+2)^2 - 4k)) / 2가 자연수여야 YES가 된다.

 

# BaekJoon20444.py

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


def solve():
    global n, k
    value = (n + 2) ** 2 - 4 * k

    # 근이 무리수가 아니어야함
    if value < 0:
        print("NO")
        return

    # 근이 정수여야 함
    if int(value ** 0.5) ** 2 != value:
        print("NO")
        return

    first = ((n + 2) - value ** 0.5) / 2
    second = ((n + 2) + value ** 0.5) / 2

    # 2로 나눴을 때 정수여야 함
    if int(first) != first or int(second) != second:
        print("NO")
        return

    # 근이 자연수여야 함
    if first > 0 and second > 0:
        print("YES")
        return

    print("NO")

solve()