3587jjh   6년 전

거의 모든 분들이 A(m, n) = 가로 m, 세로 n인 직사각형의 최소 분할 갯수로 정의해서

가로/세로를 어떤 분할선으로 나눠서 둘로 쪼갰을때 (왼쪽파트 최소분할 갯수 + 오른쪽파트 최소분할 갯수)로 푸셨더라고요.

그런데 직사각형을 정사각형으로 채울때 그런 분할선이 안 존재하게 채울수 있음에도 불구하고

이렇게 풀면 답이 나오는 이유가 뭔가요?

분할선이 안 존재함 ex)

같은 숫자는 같은 정사각형임

00022

00022

00033

44633

44559

78551


추가)

그리고 이 문제가 가로, 세로가 특정 관계를 만족할때

A(m, n) = 1 + A(m - n, n) 이라는 것을 알지 못하면 시간초과를 피할수 없어보이는데

실제로 이 문제를 풀때 이것을 무슨 수로 떠올려야하나요. 수학 올림피아드 문제라도 평소에 풀라는건가요

풀고도 너무 찝찝하네요

jh05013   6년 전

분할선이 존재하도록 조건이 설정되어 있습니다.

3587jjh   6년 전

오 그러네요, 감사합니다

댓글을 작성하려면 로그인해야 합니다.