1. 문제
https://www.acmicpc.net/problem/17779
2. 풀이
삼성 SW 역량테스트 문제입니다. 풀이 순서는 아래와 같습니다.
- x, y, d1, d2 의 가능한 모든 수에 대하여 for문으로 동작시켰습니다. out of index 여부로 불가능 한 경우에는 건너뜁니다.
- 각 구역에서 공통되는 부분을 찾아보았습니다. 아래와 같이 직사각형으로 이루어진 부분과 감소하는 부분으로 이루어져있습니다. 해당 부분의 index를 체크하여 문제를 해결해줍니다.
참고사항은 아래와 같습니다.
- 중간에 복붙을 하다가 다른 값을 써버린 케이스가 있는데, 항상 헷갈리지 않게 변수를 자주 사용하는 것이 좋을 것 같습니다.
- 다른 사람의 경우 경계선과 다른 번호가 만나는 경계선을 미리 칠해놓고 꼭지점에서 DFS 를 수행하는 경우가 있었습니다. polynomeer.log 님의 블로그
N = int(input())
maps = [list(map(int, input().split())) for x in range(N)]
answer = 987654321
for x in range(1, N+1):
for y in range(1, N+1):
for d1 in range(1, N+1):
for d2 in range(1, N+1):
# out of index
if x+d1+d2 > N or y-d1 < 1 or y+d2 > N :
continue
is_visited = [ [False] * N for _ in range(N) ]
# 범위마다 해당하는 요소들 고르기
arr = [0] * 5
## 1번 구역
### 직사각형 구역 구하기
for r in range(1, x):
for c in range(1, y+1):
arr[0] += maps[r-1][c-1]
is_visited[r-1][c-1] = True
### 점차 감소하는 부분 구하기
# (x, 1), (x,2) ,,,, (x, y-1)
# (x+1, 1), (x+1,2) ,,,, (x+1, y-2)
# (x+d1-1, 1) ,,,,, (x+d1-1, y - d1)
search_len = d1
col_start = y - 1
row_start = x
for diff in range(0, search_len):
for r, c in [ (row_start+diff, i) for i in range(1, col_start - diff + 1)]:
arr[0] += maps[r-1][c-1]
is_visited[r - 1][c - 1] = True
## 2번 구역
### 직사각형 구역 구하기
for r in range(1, x+1):
for c in range(y+1, N+1):
arr[1] += maps[r - 1][c - 1]
is_visited[r - 1][c - 1] = True
### 점차 감소하는 부분 구하기
search_len = d2
col_start = y + 2
row_start = x + 1
for diff in range(0, search_len):
for r, c in [ (row_start + diff, i) for i in range(col_start+diff, N+1)]:
arr[1] += maps[r-1][c-1]
is_visited[r - 1][c - 1] = True
## 3번 구역
### 직사각형 구역 구하기
for r in range(x+d1+d2, N+1):
for c in range(1, y+d2-d1):
arr[2] += maps[r - 1][c - 1]
is_visited[r - 1][c - 1] = True
### 점차 감소하는 부분 구하기
search_len = d2
col_start = y - d1 + d2 - 2
row_start = x + d1 + d2 - 1
for diff in range(0, search_len):
for r, c in [ (row_start - diff, i) for i in range(1, col_start - diff + 1)]:
arr[2] += maps[r-1][c-1]
is_visited[r - 1][c - 1] = True
## 4번 구역
### 직사각형 구역 구하기
for r in range(x+d1+d2+1, N+1):
for c in range(y+d2-d1, N+1):
arr[3] += maps[r - 1][c - 1]
is_visited[r - 1][c - 1] = True
### 점차 감소하는 부분 구하기
search_len = d1
col_start = y-d1+d2+1
row_start = x+d1+d2
for diff in range(0, search_len):
for r, c in [ (row_start - diff, i) for i in range(col_start + diff, N+1)]:
arr[3] += maps[r-1][c-1]
is_visited[r - 1][c - 1] = True
## 5번 구역
for r in range(1, N + 1):
for c in range(1, N + 1):
if is_visited[r - 1][c - 1] == False:
arr[4] += maps[r-1][c-1]
# 정답 갱신
answer = min(answer, max(arr)-min(arr))
print(answer)