타일 만들기

아래 그림 왼쪽에 있는 정사각형 판을 잘라서 오른쪽에 있는 것과 같은 타일을 여러 개 만들려고 한다. 최대 몇 개의 타일을 만들 수 있는가? (단, 타일은 회전할 수 있다.)

 

출처) 정보올림피아드 2012년 초등부 1번 문제

 

정답) 5

문제풀이)

우의 그림과 같이 자르면 최대 5개까지 만들수 있다.

프로그램에서는 이러한 문제를 재귀함수와 BFS 를 이용해서 처리할 수 있다.

기준점을 하나 잡고 꼭짓점을 기준으로 잘라 나가면 최대 갯수를 만들 수 있다.