Informatica Online Judge

  꼬치구이 장인 지민 #1 [2356 / 0934]

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


The Champion of this Problem (C++) : gs18021 - ms / 1814byte
My Best Submission (C++) : N/A

[36th 김석표 (gs18021)]
Writer ID : [gs18021]

Background

준호는 "꼬치구이 장인"(Koistudy #2198, 2199) 문제에 나온 장인인 경곽이의 제자인 지민이에게 꼬치를 사러간다.

하지만 준호는 너무 배고파서, 꼬치에 재료가 3개뿐인 것으로는 만족할 수 없다!

그래서 지민이는 신메뉴를 개발해서, 재료 K개를 꽃는 꼬치를 만드려고 한다.

각 재료는 N행, M열로 구분된 격자칸에 배치되어 있다.

각 칸에 재료가 1개씩 배치되어 있다.

각각의 재료는 1 이상 K 이하의 정수 번호가 붙는다.

지민이는 왼쪽으로부터 오른쪽 방향, 또는 위로부터 아래쪽 방향으로 연속된 K칸으로부터 재료를 가져와서 꼬치에 끼워 꼬치구이를 만든다.

즉, 꼬치구이 하나에 들어가는 재료는 정확하게 K개이다.

지민이는 1, 2, ..., K번 재료가 하나씩 순서대로 구성된 꼬치구이를 최대한 많이 만들고자 한다.

꼬치구이에 끼우는 재료의 순서는 원래 격자판에서 가져온 순서대로 만들어야 한다.

또 같은 재료를 2개의 꼬치구이에 사용할 수 없다.

준호의 요구를 들어줘야 하는 지민이를 도와, 지민이가 만들 수 있는 최대 꼬치구이의 수를 구해보자.

Input

첫 번째 줄에는 N, M, K가 공백으로 구분되어 입력된다.

다음 줄부터 N줄에 걸쳐서 격자판의 배열이 주어진다. 각 줄에는 1 이상 K 이하의 정수 M개가 주어진다.

[입력값의 정의역]
1 <= N, M <= 3000
2 <= K <= 100

SubTask #1 : 1 <= N, M <= 100, 2<=K<=3

Output

만들 수 있는 최대 꼬치구이의 수를 출력한다.

IO Example

입력
3 4 3
1 2 3 1
2 1 2 2
1 2 3 3

출력
3

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