이번 문제는 브루트포스를 통해 모든 경우에 대하여 접근하며, 범위 내에 존재할 수 있는 경우에 조건에 맞게 5개의 구간으로 나누는 함수를 구현하여 구간별 인구수의 합을 리스트로 저장하고, 이 리스트에서의 최댓값과 최솟값의 차를 최종 결과 변수와 비교하여 더 작은 값으로 갱신하도록 하였다.

선거구를 나누는 방식에서는 선거구에 대한 임시 리스트를 만들고, 이를 이용하여 가장 먼저 5번 선거구를 표시하였고, 좌표를 이용하여 1~4의 선거구의 인구수를 구하였다.

4차원 for문으로 모든 인덱스에서 마름모의 가로, 세로의 길이의 모든 경우에 대하여 접근하는 것까지는 잘 하였지만, 인덱스를 표현하는 방식과 범위의 조건 처리가 까다로웠고, 이로 인해 많은 시간이 소비되었다. 결국은 다른 코드를 참고하였다. 다음 삼성 문제는 안보고 스스로 풀 예정..

• n을 입력받는다.
• a 리스트를 선언한다.
• a리스트에 값을 입력받는다. 이때 앞에 0을 붙여 인덱스가 1번부터 n번까지 유효하도록 처리한다.
• divide함수를 y, x, d1, d2를 인자로 갖도록 선언한다.
  -> 결과를 저장할 리스트 answers를 길이 6의 0으로 채워진 리스트로 선언한다.
  -> 선거구로 나눠지는 것을 표현하기 위한 2차원 리스트 chk를 (n+1)*(n+1)의 크기로 선언하고 0으로 채운다.
  -> d1만큼 반복하는 i에 대한 for문을 돌린다.
  --> chk[y+i][x-i]를 5로 갱신한다.
  --> chk[y+d2+i][x+d2-i]를 5로 갱신한다.
  -> d2만큼 반복하는 i에 대한 for문을 돌린다.
  --> chk[y+i][x+i]를 5로 갱신한다.
  --> chk[y+d1+i][x-d1+i]를 5로 갱신한다.
  -> y+1부터 y+d1+d2만큼 반복하는 i에 대한 for문을 돌린다.
  --> chk_True를 False로 선언한다.
  --> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  ---> 만약 chk[i][j]가 5일 경우,
  ----> chk_True를 not으로 변환한다.
  ---> 만약 chk_True가 True일 경우,
  ----> chk[i][j]를 5로 갱신한다. (마름모 안쪽을 5로 바꿔주는 과정)
  -> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  --> 1부터 n까지 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 i<y+d1 and j<=x and chk[i][j]==0가 성립할 경우,
  ----> answers[1]에 a[i][j]를 더한다.
  ---> 만약 i<=y+d2 and x<j and chk[i][j]==0가 성립할 경우,
  ----> answers[2]에 a[i][j]를 더한다.
  ---> 만약 y+d1<=i and j<x-d1+d2 and chk[i][j]==0가 성립할 경우,
  ----> answers[3]에 a[i][j]를 더한다.
  ---> 만약 y+d2<i and x-d1+d2<=j and chk[i][j]==0가 성립할 경우,
  ----> answers[4]에 a[i][j]를 더한다.
  ---> 만약 chk[i][j]가 5일 경우,
  ----> answers[5]에 a[i][j]를 더한다.
  -> max(answers[1:])-min(answers[1:])를 반환한다.
• 결과 변수 answer를 sys.maxsize로 선언한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> n번 반복하는 j에 대한 for문을 돌린다.
  --> n번 반복하는 d1에 대한 for문을 돌린다.
  ---> n번 반복하는 d2에 대한 for문을 돌린다.
  ----> 만약 0<i<i+d1+d2<=n and 0<j-d1<j<j+d2<=n가 성립할 경우,
  -----> answer를 answer과 divide(i, j, d1, d2)의 반환값 중의 최솟값으로 갱신한다.
• answer를 출력한다.

Code

import sys
n=int(input())
a=[[]]
for i in range(1, n+1):
    a.append([0]+list(map(int, input().split())))
def divide(y, x, d1, d2):
    answers=[0 for _ in range(6)]
    chk=[[0 for _ in range(n+1)] for _ in range(n+1)]
    for i in range(d1+1):
        chk[y+i][x-i]=5
        chk[y+d2+i][x+d2-i]=5
    for i in range(d2+1):
        chk[y+i][x+i]=5
        chk[y+d1+i][x-d1+i]=5
    for i in range(y+1, y+d1+d2):
        chk_True=False
        for j in range(1, n+1):
            if chk[i][j]==5:
                chk_True=not chk_True
            if chk_True:
                chk[i][j]=5
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i<y+d1 and j<=x and chk[i][j]==0:
                answers[1]+=a[i][j]
            elif i<=y+d2 and x<j and chk[i][j]==0:
                answers[2]+=a[i][j]
            elif y+d1<=i and j<x-d1+d2 and chk[i][j]==0:
                answers[3]+=a[i][j]
            elif y+d2<i and x-d1+d2<=j and chk[i][j]==0:
                answers[4]+=a[i][j]
            elif chk[i][j]==5:
                answers[5]+=a[i][j]
    return max(answers[1:])-min(answers[1:])
answer=sys.maxsize
for i in range(n):
    for j in range(n):
        for d1 in range(n):
            for d2 in range(n):
                if 0<i<i+d1+d2<=n and 0<j-d1<j<j+d2<=n:
                    answer=min(divide(i, j, d1, d2), answer)
print(answer)