백준 20444 (색종이와 가위)
백준 20444 (색종이와 가위)
문제 링크
문제 링크 : https://www.acmicpc.net/problem/20444
문제 접근
1) 1x1의 사각형에서 가로 방향으로 자르면 2x1(세로로 2개, 가로로 1개 -> 2차원 배열이라고 생각하시면 편합니다.)의 사각형 혹은 1x2 사각형이 나옵니다.
이를 확장해보면, axb 사각형에서 자르는 방향 관계없이 나오는 사각형은 (a+1)xb, ax(b+1)이 될 것입니다.
2) 자르는 순서는 관계 없습니다. 즉 axb 모양을 만들기 위해 가로 세로 어느 방향으로 잘라도 횟수만 맞으면 상관 없습니다.
3) axb를 만들기 위해 가로 방향으로는 a-1번, 세로 방향으로는 b-1번 잘라야 합니다.
입력으로 횟수(n), 잘린 사각형 수(k)가 주어집니다.
(a-1)+(b-1)=n, axb=k 라고 쓸 수 있는데, 정리해보면 a+b=n+2, axb=k입니다.
이차함수에서 근과 계수의 관계가 생각이 났습니다.
정리해보자면, 두 근 a,b(a,b는 1 이상의 정수)를 갖고, a+b=n+2, ab=k인 이차함수가 조건을 만족하는 실근을 갖는지 판단하는 문제로 치환할 수 있습니다.
4) 이를 판단하기 위해 먼저 이차함수 ax^^2+bx+c=0에서 판별식 D=b**2-4ac가 0보다 작다면 실수해를 갖지 않으므로 한 번 걸러주고, 두 번째로 두 실근이(같을수도(D==0) 다를수도(D>0) 있습니다.) 1보다 큰 정수라면 YES를 출력하고 그렇지 않다면 NO를 출력하도록 구현하였습니다.
5) 이 문제를 처음 풀 때 18%에서 계속 멈췄었는데, 큰 숫자의 루트 연산에서 오류가 났다고 생각을 했습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys
n,k=map(int,sys.stdin.readline().split())
d=(n+2)**2-4*k
if d<0 :
print("NO")
else : #d>=0
if (d**0.5).is_integer(): #--error point--
d=(d**0.5)
sol1=((n+2)+d)/2
sol2=((n+2)-d)/2
if sol1>=1 and sol2>=1 :
if sol1.is_integer() and sol2.is_integer():
print("YES")
else :
print("NO")
else :
print("NO")
else :
print("NO")
이게 초기 소스코드인데 오류가 있습니다. d가 매우 큰 수에 루트까지 씌운 형태이므로, 이 과정에서 부동소수점 오류가 발생하기 때문입니다. 따라서 이를 방지하기 위해서 d에 루트를 씌운 후, 제곱을 한 값이 처음과 같다면 정수라고 판단하도록 코드를 작성하였습니다.
1
int(d**0.5)**2==d:
이렇게 수정하면 정답이 됩니다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys
n,k=map(int,sys.stdin.readline().split())
d=(n+2)**2-4*k
if d<0 :
print("NO")
else : #d>=0
if int(d**0.5)**2==d:
sol1=((n+2)+d**(0.5))/2
sol2=((n+2)-d**(0.5))/2
if sol1>=1 and sol2>=1 :
if sol1.is_integer() and sol2.is_integer():
print("YES")
else :
print("NO")
else :
print("NO")
else :
print("NO")
마무리하며
큰 수의 부동소수점 오류는 항상 신경써야 하는 문제입니다. 딱 오류가 날 법 한 곳에서 오류를 찾아서 그나마 기분이 좋았습니다. 내부 메소드 신봉은 하지 말아야겠습니다.