[SWEA] 2805.농작물 수확하기/Python - D3

❓문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB

SW Expert Academy

성능 요약

메모리: 50,364 KB, 시간: 174 ms, 코드길이: 422 Bytes

✍🏻풀이

수확할 수 있는 영역의 모양을 보면 마름모꼴이다.
마름모꼴을 삼각형으로 나눠 수확한 것의 가치를 계산하려고 한다.
n이 5일 때, 상삼각형을 먼저 확인해보겠다.
0~1까지 봤을 때, (0, 2), (1, 1), (1, 2), (1, 3)을 수확할 수 있다.
리스트를 슬라이스 영역을 어떻게 지정할지 고민했다. 2 - 0 : 2 + 0 + 1로 슬라이스하면 (0, 2)만 가져온다.
그리고 2 - 1 : 2 + 1 + 1로 슬라이스하면 (1, 1), (1, 2), (1, 3)을 가져온다.
상삼각형은 mid - j : mid + j + 1 로 범위를 지정하면 된다는 것을 알 수 있다.
이제 하삼각형을 확인해보겠다.
2~4까지 보면 (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (4, 2)을 수확할 수 있다.
하삼각형도 범위를 찾아보면 j - mid : n - j + mid로 범위를 지정하면 된다는 것을 알 수 있다.

💻코드

t = int(input())
for i in range(1, t + 1):
    n = int(input())
    farm = [list(map(int, input().strip())) for _ in range(n)]

    if n == 1:
        print(f"#{i} {farm[0][0]}")

    else:
        res = 0
        mid = n//2
        for j in range(mid):
            res += sum(farm[j][mid - j:mid + j + 1])

        for j in range(mid, n):
            res += sum(farm[j][j - mid:n - j + mid])

        print(f"#{i} {res}")

📍후기

대학교 1학년 때 시험 문제에서 본 마름모 문제가 떠올랐는데 엥 설마 단순 구현은 아니겠지라고 생각하면 BFS로 시도한다는..
다른 사람들 찾아보니 반복문이길래 바로 코드 다 지우고 범위찾기했다.