10803번 - 정사각형 만들기
거의 모든 분들이 A(m, n) = 가로 m, 세로 n인 직사각형의 최소 분할 갯수로 정의해서
가로/세로를 어떤 분할선으로 나눠서 둘로 쪼갰을때 (왼쪽파트 최소분할 갯수 + 오른쪽파트 최소분할 갯수)로 푸셨더라고요.
그런데 직사각형을 정사각형으로 채울때 그런 분할선이 안 존재하게 채울수 있음에도 불구하고
이렇게 풀면 답이 나오는 이유가 뭔가요?
분할선이 안 존재함 ex)
같은 숫자는 같은 정사각형임
00022
00033
44633
44559
78551
추가)
그리고 이 문제가 가로, 세로가 특정 관계를 만족할때
A(m, n) = 1 + A(m - n, n) 이라는 것을 알지 못하면 시간초과를 피할수 없어보이는데
실제로 이 문제를 풀때 이것을 무슨 수로 떠올려야하나요. 수학 올림피아드 문제라도 평소에 풀라는건가요
풀고도 너무 찝찝하네요
분할선이 존재하도록 조건이 설정되어 있습니다.
오 그러네요, 감사합니다
댓글을 작성하려면 로그인해야 합니다.
3587jjh 6년 전
거의 모든 분들이 A(m, n) = 가로 m, 세로 n인 직사각형의 최소 분할 갯수로 정의해서
가로/세로를 어떤 분할선으로 나눠서 둘로 쪼갰을때 (왼쪽파트 최소분할 갯수 + 오른쪽파트 최소분할 갯수)로 푸셨더라고요.
그런데 직사각형을 정사각형으로 채울때 그런 분할선이 안 존재하게 채울수 있음에도 불구하고
이렇게 풀면 답이 나오는 이유가 뭔가요?
분할선이 안 존재함 ex)
같은 숫자는 같은 정사각형임
00022
00022
00033
44633
44559
78551
추가)
그리고 이 문제가 가로, 세로가 특정 관계를 만족할때
A(m, n) = 1 + A(m - n, n) 이라는 것을 알지 못하면 시간초과를 피할수 없어보이는데
실제로 이 문제를 풀때 이것을 무슨 수로 떠올려야하나요. 수학 올림피아드 문제라도 평소에 풀라는건가요
풀고도 너무 찝찝하네요