Informatica Online Judge

  야채밭 가꾸기 [1077 / 0435]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 11   Total Tried : 20


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

n × m 크기의 밭을 구입한 병찬이는 이 밭에 다양한 야채들을 심어 보려는 계획 중이다. 하지만 병찬이에게는 다음 세 가지 문제가 있어 이를 해결해야 한다.

(1) 정사각형 형태로만 야채를 심을 수 있다.
(2) 같은 야채가 심어져 있다는 것은 서로 같은 정사각형의 영역에 포함된다고 가정한다.

예를 들어, 1 × 3 크기를 밭을 구입하였다면 정사각형을 만들 수 있는 크기가 1이므로 "1" 야채를 심고 다음 크기 1에는 "1" 야채를 심을 수 없다.

왜냐하면 같은 야채를 심으려면 반드시 정사각형의 형태를 이뤄야 하는데 직사각형이 되기 때문이다.

그러므로 "1"이 아닌 다른 야채 "2"를 심어야 한다. 마찬가지로 3번째 영역에 "2"는 심을 수 없다. 하지만 앞에 심었던 "1"을 심어도 된다. 즉, "1 2 1"의 형태로 야채의 종류 2가지로 밭을 채울 수 있다.

n × m 크기의 밭에 야채를 심는 방법을 출력하라. 단, 각 야채의 종류는 숫자 1, 2, 3, ...을 사용하며 만일 밭에 야채를 심는 방법이 여러 가지가 되면 행 우선으로 봤을 때, 사전순에서 빠른 것을 출력한다.

예를 들어, 1 × 3의 밭에 야채를 심는 방법은 "1 2 1", "2 1 2", "3 4 5" 등 다양할 수 있으나 가장 야채의 종류를 적게 심으면서 사전순으로 가장 빠른 것은 "1 2 1"이므로 "1 2 1" 출력한다.

* 참고사항 : 행우선 읽기

만약 2행 3열이라면

1 2 3
4 5 6

순으로 읽어 나가는 것이 행우선 읽기이고

1 3 5
2 4 6

순으로 읽어 나가는 것이 열우선입니다.

Input

두 개의 정수 n과 m이 주어진다. 

[Sub-Task Info]
- 100%의 데이터는 행과 열이 100이하의 자연수이다. (모두 각각 채점됨)

Output

밭에 심겨진 야채들의 배치 모양을 출력한다. 여러 가지 경우가 있으므로 행우선으로 읽을 때 가장 사전순으로 빠른 모양을 추력한다.

IO Example

입력1
1 3

출력1
1 2 1

입력2
2 2

출력2
1 1
1 1

입력3
3 4

출력3
1 1 1 2
1 1 1 3
1 1 1 2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]