[SWEA] #11014. 농작물 수확_파이썬

문제 💎

11014. 03_배열2_농작물 수확

* 문항 설명에 오류가 있다. 비용에 관해서 생각하지 말고, 밭을 나눠가졌을 때 가장 공평하게 가질 수 있는 값에 대해서만 생각하도록 한다. 

입력으로 N X N 크기의 농장에 대한 정보가 2차 배열 형태의 값들이 주어진다. 주어진 값들은 각 셀에서 얻을 수 있는 농작물의 양이다.

수민, 기라, 현석 3형제는 농장을 3분할 해서 농작물을 나눠 가질 계획이다.

욕심많은 수민이 때문에 형제간 불화가 생기지 않도록 최대한 공평하게 나누어야 한다.

농장을 3분할 하는 방법은 가로선과 세로선을 그어서, 다음 그림과 같이 3개의 영역으로 나누는 것이다.

사각영역의 가로와 세로의 크기는 최소 1이상이어야 한다.

3 분할 했을 때 세 영역에서 얻을 수 있는 농작물 총합의 최대값과 최소값의 차이가 최소가 되는 경우를 찾아보자.


[입력조건]

첫 줄에 테스트케이스 수가 주어진다.

각 테스트 케이스마다 첫 줄은 땅의 크기 N과 농지의 크기 R, C 가 주어진다.

다음 N개의 줄에 각 셀을 농지로 만드는 비용이 주어진다. 비용은 0 ~ 9 사이의 값이다.

[출력조건]

#〉 과 케이스 번호를 출력하고 농지를 만들기 위한 최소 비용을 출력한다.

입력

3
5
2 3 2 2 1
3 1 1 1 3
3 2 3 1 3
1 1 3 2 1
2 2 2 1 1
5
3 3 2 1 1
2 1 1 3 1
3 1 3 3 2
3 1 2 2 3
2 3 1 2 2
5
1 3 2 1 3
3 1 3 2 1
3 3 1 1 2
1 3 2 2 1
1 2 3 3 2
 

출력

#1 7
#2 8
#3 6

 

풀기 전 생각해보기😮

• 밭을 나눴을 때 세 사람이 갖는 값의 양 탐색하기
• 가장 균등한 지점과 가까운 곳 찾기

---

풀이🛫

# 농작물 수확
 
T = int(input())
 
for t in range(T):
    N = int(input())
    field = [list(map(int, input().split())) for i in range(N)]
 
    li_one, li_two, li_three, li_other = [], [], [], []
 
    for vl in range(N):
        for hl in range(N):
            one, two, three, other = 0, 0, 0, 0
            for col in range(N):
                for row in range(N-vl):
                    three += field[col][row+vl]
 
            li_three.append(three)
             
            for col in range(hl):
                for row in range(vl):
                    one += field[col][row]
            li_one.append(one)
 
            for col in range(N-hl):
                for row in range(vl):
                    two += field[col+hl][row]
             
            li_two.append(two)
 
    li_sigma = []
    zip_field = list(zip(li_three, li_one, li_two))
    for i in zip_field:
        tot = 0
        for j in i:
            tot += ((sum(i)/3)-j)**2
            sigma = tot/3
        li_sigma.append(sigma)
 
 
    sigma_index = li_sigma.index(min(li_sigma))
 
    answer = max(zip_field[sigma_index])-min(zip_field[sigma_index])
 
    print("#"+str(t+1), answer)

 

핵심 정리🎁

• 3번 사람의 경우를 먼저 검토하고, 1번, 2번이 가질 수 있는 값을 탐색한다
  1, 2번 사람의 값을 찾기 위해 가로로 선을 그엇을 때 3번 값에 영향을 미치는 세로선(vl)에 따라 값이 달라진다.
  반면 3번 사람의 값은 1, 2번이 갖는 값과 별개로 vl 지점을 가정해서 찾을 수 있다.
  따라서 3번의 값을 먼저 생각해보고 난 후 1, 2번의 값을 찾는다. 
  
  
• 리스트의 범위를 지정할 때 실수를 범하지 않도록 주의하자
  row+vl, col+hl 등의 인덱스 위치를 설정할 때 스스로 너무 헷갈려했다. range값에 따라 row 또는 col은 0의 인덱스부터 탐색을 시작한다. 그러나 0이 아닌 선이 그어진 곳부터 탐색을 진행해야 하므로, vl 또는 hl을 더해주어야 했다. 
  
  
• 가장 비슷한 값을 나눠가지도록 확인하는 코드에 대한 아이디어가 부족했다. 분산의 크기를 구해서 가장 작은 값에 해당하는 1, 2, 3의 값을 비교하는 방식으로 대체했다. 더 좋은 풀이 방법에 대해서는 아직 잘 모르겠다.

 

후기 😎

• 확실히 이과생, 특히 공대생 분들은 코트 풀이에 강해보였다. 나의 경우 col, row, vl, hl 등 코드의 모든 인자에 대해서 확신이 없으면 중도에 길을 잃어버리기 마련인데, 단순히 3중 ~ 4중 for문을 이용하고, 변수명도 단순히 사용해서 풀어내는 분들의 코드를 보면 특히나 더 노력해야 비슷해질 수 있나보다 싶었다.
  
  
• 요즘 우영우로 잘나가는 박은빈님의 명언 영상을 보면서 풀이를 마무리 해보았다.
  "그래도 어쩌겠습니까 잘 해내야죠"
  https://youtube.com/shorts/IGWZy9mlg9g?feature=share