근의 공식
-
[백준] Python - 색종이와 가위메모/알고리즘 2021. 11. 2. 22:37
20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 색종이와 가위 문제다. 이진탐색 문제라고는 하지만 이진탐색을 쓸 필요는 없다. 색종이를 잘랐을때 입력한 값 만큼의 사각형이 나오는지 판단하는 문제이다. 여기서 규칙이 하나 생기는데 x를 가로로 자르는 횟수, y를 세로로 자르는 횟수, n을 총 자르는 횟수, k를 잘랐을 때 나오는 사각형의 총 개수라고 하면 1) x + y = n 2) (x+1)(y+1) = k가 성립한다. 여기서 1)에서 x = n - y를 2)에 대입하면 x에 대한 2차 방정식이 나온다. 사각형의 개수는 무조건 자연수일 수 밖에 없으니 이 2차 방정식을 근의 공식을 통해 해가 자연수로 나오..