[SWEA] #4301 콩 많이 심기

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWLv-yZah48DFAVV

계획

두 콩 사이의 거리가 2가 되면 안 되므로 상하좌우 네 방향으로 2칸 띄운 위치에 콩이 있는지 확인하고, 상하좌우 모든 위치에 콩이 없을 때에만 현재 위치에 콩을 놓을 수 있다. 따라서 모든 위치에 대해서 델타 탐색을 한 뒤 조건을 만족할 때에만 값을 +1 해주는 식으로 풀고자 했다.

코드

delta = [[-2, 0], [0, -2]]

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    arr = [[0] * N for _ in range(M)]
    result = 0

    for i in range(M):
        for j in range(N):
            flag = True
            # 2칸 왼쪽 or 2칸 위쪽에 콩이 있는지 확인
            for k in range(2):
                tx = i + delta[k][0]
                ty = j + delta[k][1]
                # 콩이 있으면 flag 값 변경
                if 0 <= tx < M and 0 <= ty < N and arr[tx][ty]:
                    flag = False
                    break
            # 왼쪽, 위쪽에 콩이 없을 때만 콩을 놓음
            if flag:
                arr[i][j] = 1
                result += 1

    print('#{} {}'.format(tc, result))

풀이 방법

처음에 네 방향 델타 탐색으로 풀었을 때 for문에서 M과 N을 반대로 써서 시간초과가 났었다. 가로 세로 길이 제대로 확인하자..
그리고 for문에 따라 왼쪽에서 오른쪽으로, 위에서 아래로 확인하기 때문에 오른쪽/아래쪽에 콩이 있을 수 없다. 그래서 왼쪽/위쪽 2가지 방향에 대해서만 델타 탐색을 하도록 코드를 변경하여 실행 시간을 줄일 수 있었다.