리퍼는 직사각형으로 도형을 색칠하는 방법을 2가지 발견했다.
첫 번째 방법은 다음과 같다.
1. 임의의 한 점을 찍는다.
2. 1번에서 찍은 점을 가로로 최대한 늘린다.
3. 2번에서 만든 선을 세로로 최대한 늘린다.
4. 도형이 모두 채워질 때까지 1~3번 과정을 반복한다.
이를 1번 방법이라 한다.
두 번째 방법은 다음과 같다.
1. 임의의 한 점을 찍는다.
2. 1번에서 찍은 점을 세로로 최대한 늘린다.
3. 2번에서 만든 선을 가로로 최대한 늘린다.
4. 도형이 모두 채워질 때까지 1~3번 과정을 반복한다.
이를 2번 방법이라 한다.
예를 들어서, 아래와 같은 도형이 있을 때
이 도형을 1, 2번 방법으로 칠한다면
1번 방법:
이 때 이 도형은 2개의 직사각형으로 채워지며, 이는 이 도형을 채울 수 있는 직사각형의 최소 개수다.
2번 방법:
이 때 이 도형은 2개의 직사각형으로 채워지며, 이 역시 이 도형을 채울 수 있는 직사각형의 최소 개수다.
여기서 같은 크기의 정사각형으로 이뤄진 임의의 도형이 있다고 할 때
이 도형을 1번 방법으로 칠했을 때 생기는 직사각형의 최소 개수를 a1,
2번 방법으로 칠했을 때 생기는 직사각형의 최소 개수를 a2라고 하자.
a1와 a2의 크기는 항상 같을까? 맞다면 이를 증명하고, 아니라면 반례를 들어라.
(반례를 들 때는 도형을 그려서 올리면 된다.)
좋아요
5
글쎄요
1
어려워요
2