SWEA 4301. 콩 많이 심기 (Python)(D4)

문제

콩을 사랑하는 민석이의 취미는 n*m 크기의 사각형 밭에 콩을 늘어놓는 것이다.

한 칸에 콩 하나씩을 놓을 수 있는데, 2가 싫은 민석이는 콩들 사이의 길이가 2가 되지 않도록 하면서 최대한 많은 콩을 놓으려고 한다.

예를 들어 다음과 같이 콩을 배치할 수 없다.

콩1(x1, y1)과 콩2(x2, y2) 사이의 길이는



이다.

민석이를 도와서 사각형 밭에 최대로 콩을 늘어놓자.


[입력]

첫째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 10)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 가로길이 N, 세로길이 M이 주어진다.

(1 ≤ N, M ≤ 1000)

[출력]

각 테스트 케이스마다 밭에 놓을 수 있는 콩의 최대 개수를 출력하라.

[HINT]

3*2 밭에 콩을 배치하는 경우 다음과 같이 최대 4개를 배치할 수 있다.

풀이

• 이차원 배열을 전부 순회한다.
• 해당칸이 0(심기가능한 상태)일 경우, 콩을심는다
  - 오른쪽+2칸이 이차원배열 범위 안일경우, -1(심기불가능)
  - 아래+2칸이 이차원배열 범위 안일경우, -1(심기불가능)

res=[]
for m in range(int(input())):
    tmp=0
    N,M=map(int,input().split())
    li=[[0]*(N) for i in range(M)]
    for i in range(M):
        for j in range(N):
           if li[i][j]==0:
            li[i][j]=1
            tmp+=1
            if i+2<M:
                li[i+2][j]=-1
            if j+2<N:
                li[i][j+2]=-1
    res.append(tmp)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))