백준 17547 Floor plan 풀이

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

17547번: Floor Plan

영어로 된 문제지만 쫄지마세요. 

n이 주어졌을때 $$ n = m^2-k^2 $$ 위 수식을 만족하는 m과 k를 구하면 됩니다. 해가 없다면 impossible 을 출력하면 끝. 

 

이 문제 풀이는 수포자가 적는 풀이로 제대로 된 이해를 바탕으로 쓴 글이 아닐지도 모릅니다. 이 문제 푼 사람을 붙잡고 계속 물어보고 수식을 보다보니 저절로 외워진 부분도 있습니다. 개인적으로 어려웠던 문제인만큼 최대한 풀어서 써보겠습니다. 

 

풀이

 

제곱수와 제곱수를 뺀 값의 규칙을 찾으면 됩니다.

 

(k+1)^2 식을 전개하면 아래와 같은 수식이 나옵니다.

 

$$ (k+1)^2 - k^2  = 2k+1 $$

 

제곱수 - 제곱수의 수식 형태이므로 n이 존재합니다. 이런 경우에는 해가 m = n/2+1,k = n/2겠죠.

이때의 n은 홀수입니다. n = 2k+1이라고 할때, 2인 짝수와 k를 곱하면 무조건 짝수가 나오고 거기에 1을 더하니까 무조건 홀수입니다.

 

따라서 모든 홀수인 n은 m = n/2+1,k = n/2 을 가집니다.

 

 

$$ (k+2)^2 - k^2 = 4k+4 $$

 

이 수식도 해가 존재하겠죠?? 해는 m = n/4+1,k = n/4-1 입니다.  이 경우의 n은 4의 배수입니다. 4와 k를 곱한 값은 4의 배수. 거기에 4를 더해도 4의 배수가 나오죠ㅎㅎ 

 

이외의 짝수는 해가 존재하지 않습니다.

 

코드

 

n=int(input())

if n%2==1:
	print(n//2+1, n//2)
elif n%4==0:
	print(n//4+1, n//4-1)
else:
    print("impossible")