Python으로 푸는 SW Expert Academy 2805. 농작물 수확하기

SW Expert Academy 2805. 농작물 수확하기

이 문제는 농장에서 특정 규칙에 맞춰서 수확할 수 있는 범위가 정해져 있고

그 규칙에 따라 농작물을 수확했을 때 총 수익이 얼마인지 구할 수 있도록 구현해야 한다.

삼성 SW Expert Academy에서 푼 문제 리스트 보기

github에서 코드 보기

문제 조건

- 농장의 크기는 항상 홀수이다. (1 X1, 3 X 3, ....49 X 49)

- 수확은 아래와 같이, 항상 농장의 크기에 딱 맞는 정사각형 마름모 형태로만 가능하다.

제약 사항

농장의 크기 N은 1이상 49 이하의 홀수이다. (1 <= N <= 49)

농작물의 가치는 0~5이다.

문제 풀이

처음에는 문제를 잘못 이해하는 바람에 파란색 위치의 농장물의 숫자에 규칙이 있는 줄 알고 한참을 들여다 보았었다.

근데 그냥 파란색 마름모 모양이 N의 크기가 커짐에따라 점점 커진다는게 규칙이다.

농장의 정 가운데 (N-1) / 2 번째의 가로, 세로줄은 모두 수확 가능한 부분이다.

N이 7일때,

각 가로줄 마다 수확가능한 밭의 수는 1, 3, 5, 7, 5, 3, 1 로 점점 늘어나다가 줄어든다.

결국 N 이하의 홀수를 나열하고 왕복하면 그게 각 가로줄마다 수확할 수 있는 농장의 수이다.

(편의를 위해 내 코드에서는 N의 최대 숫자인 49까지의 홀수를 미리 구해둔다.)

3번째 지점을 중심으로 추가되는 밭의 수는 왼쪽 오른쪽으로 균등하게 나눠진다. 

이 점을 이용하여 각 가로줄마다 수확가능한 밭의 시작 Index와 끝 Index를 찾아 그 부분의 합을 더해간다.

	0	1	2	3	4	5	6	양 쪽에 추가할 밭의 수 (p)	수확 범위 추출 ( farm[r][3 - p : 3 + p + 1])
0								(1-1) // 2 = 0	farm[0][3:4]
1								(3-1) // 2 = 1	farm[1][2:5]
2								(5-1) // 2 = 2	farm[2][1:6]
3								(7-1) // 2 = 3	farm[3][0:7]
4								(5-1) // 2 = 2	farm[4][1:6]
5								(3-1) // 2 = 1	farm[5][2:5]
6								(1-1) // 2 = 0	farm[6][3:4]

파이썬 코드

def solve(n, lines, capicity_list):
    middle_index = (n - 1) // 2
    r = 0
    revenue = 0
    for length in capicity_list:
        side = (length - 1) // 2
        start_index = middle_index - side
        end_index = middle_index + side + 1
        revenue += sum(lines[r][start_index:end_index])
        r += 1
    
    for length in reversed(capicity_list[:-1]):
        side = (length - 1) // 2
        start_index = middle_index - side
        end_index = middle_index + side + 1
        revenue += sum(lines[r][start_index:end_index])
        r += 1
    return revenue
 
if __name__ == "__main__":
    
    n = 1
    odd = []
    while n < 50:
        odd.append(n)
        n += 2
 
    t = int(input())
    for c in range(t):
        n = int(input())
        odd_index = odd.index(n)
        lines = []
        for i in range(n):
            lines.append(list(map(int, list(input().strip()))))
        print("#{0} {1}".format(c+1, solve(n, lines, odd[:odd_index+1])))

#sw expert 2805 #sw expert 2805 농작물 수확하기 #2805 농작물 수확하기 #python 농작물 수확하기