SWEA 2805번: 농작물 수확하기 (D3) - Python 풀이

문제 설명

SW Expert Academy

N X N크기의 농장이 있다.

이 농장에는 이상한 규칙이 있다.

규칙은 다음과 같다.

① 농장은 크기는 항상 홀수이다. (1 X 1, 3 X 3 … 49 X 49)
② 수확은 항상 농장의 크기에 딱 맞는 정사각형 마름모 형태로만 가능하다.

1 X 1크기의 농장에서 자라는 농작물을 수확하여 얻을 수 있는 수익은 3이다.
3 X 3크기의 농장에서 자라는 농작물을 수확하여 얻을 수 있는 수익은 16 (3 + 2 + 5 + 4 + 2)이다.
5 X 5크기의 농장에서 자라는 농작물의 수확하여 얻을 수 있는 수익은 25 (3 + 2 + 1 + 1 + 2 + 5 + 1 + 1 + 3 + 3 + 2 + 1)이다.

농장의 크기 N와 농작물의 가치가 주어질 때, 규칙에 따라 얻을 수 있는 수익은 얼마인지 구하여라.

[제약 사항]

농장의 크기 N은 1 이상 49 이하의 홀수이다. (1 ≤ N ≤ 49) 농작물의 가치는 0~5이다.

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스에는 농장의 크기 N과 농장 내 농작물의 가치가 주어진다.

[출력]

각 줄은 '#t'로 시작하고, 공백으로 농장의 규칙에 따라 얻을 수 있는 수익을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

입력

1
5
14054
44250
02032
51204
52212

input.txt

출력

#1 23

output.txt

풀이 과정

이 문제는 결국 N*N의 2차원 배열에서 특정 위치의 값이 ‘농장의 크기에 딱 맞는 정사각형 마름모’에 포함되는지 포함되지 않는지를 따지면 되는 문제입니다.

그래서 행별로 어떤 열의 값이 마름모의 범위에 포함되는지 적어 보았더니 규칙을 찾을 수 있었습니다.

(N-1)을 2로 나눈 값이 마름모의 중간 부분, 행의 중간값이 되고 중간값까지의 행은 열의 범위가 좌우로 한칸씩 확장되다가 중간값 이후의 행은 열의 범위가 좌우로 한칸씩 줄어들게 됩니다. 그래서 행의 중간값을 mid라는 변수에 두고 기준점 삼아 중간값 이전과 이후에 범위를 다르게 설정했습니다.

정답 코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    farm = [[] for _ in range(N)]
    for i in range(N):
        farm[i] = list(map(int, input()))
 
    revenue = 0
    # 중간행
    mid = (N-1) // 2
    for i in range(N):
        # 중간행 전까지
        if i < mid:
            # mid-i 열부터 mid+i 열까지의 합
            revenue += sum(farm[i][mid-i:(mid+i)+1])
        # 중간행 이후부터
        else:
            # i-mid 열부터 N-(i-mid) 열까지의 합
            revenue += sum(farm[i][i-mid:N-(i-mid)])
 
    print("#%d %d" %(test_case, revenue))

이상입니다.