삼성 기출문제이다. 저번에 푼 문제도 그렇고 삼성 문제들은 계산량이 많은 것이 특징이다.
문제 이해 및 적용하기
테트리스와 같은 여러 도형들이 5가지(+ 도형은 회전 가능)가 있는데 이안에 들어가는 숫자의 합이 가장 큰 경우의 숫자의 합을 출력하는 문제이다.
본인은 완전탐색의 방법으로 풀이하였다. 마지막 ㅗ 도형을 제외하고는 dfs로 풀고 ㅗ도형만 완전탐색으로 푸는 사람들도 있었다.
dx = [[0,1,2,3],[0,1,0,1],[0,0,0,1],[0,0,1,1],[0,1,1,2]]
dy = [[0,0,0,0],[0,0,1,1],[0,1,2,2],[0,1,1,2],[0,0,1,0]]
convertedDx = [[0,-1,-2,-3],[0,-1,0,-1],[0,0,0,-1],[0,0,-1,-1],[0,-1,-1,-2]]
convertedDy = [[0,0,0,0],[0,0,-1,-1],[0,-1,-2,-2],[0,-1,-1,-2],[0,0,-1,0]]
rot = [[0,1],[0],[0,1,2,3,4,5,6,7],[0,1,4,5],[0,1,2,3]]
도형의 좌표들과 이를 convert시킨 값들을 저장해두었다. 또한, rotation이 각 도형마다 중복되는 부분이 있기 때문에 각 도형의 경우의 수 만큼만 loop를 돌도록 중복된 경우는 제외된 경우의 수를 저장해주었다.
maxSum = 0
# cases of squares
for i in range(5):
# iterate map
for k in range(N):
for l in range(M):
# cases of rotation
for j in range(len(rot[i])):
curRot = rot[i][j]
curDx = []
curDy = []
if curRot == 0:
curDx = dx[i]
curDy = dy[i]
elif curRot == 1:
curDx = convertedDy[i]
curDy = dx[i]
elif curRot == 2:
curDx = convertedDx[i]
curDy = convertedDy[i]
elif curRot == 3:
curDx = dy[i]
curDy = convertedDx[i]
elif curRot == 4:
curDx = dx[i]
curDy = convertedDy[i]
elif curRot == 5:
curDx = convertedDy[i]
curDy = convertedDx[i]
elif curRot == 6:
curDx = convertedDx[i]
curDy = dy[i]
elif curRot == 7:
curDx = dy[i]
curDy = dx[i]
if l+max(curDx) < M and k+max(curDy) < N and l+min(curDx) >=0 and k+min(curDy) >= 0:
sumOfSquare = 0
for p in range(4):
sumOfSquare+=maplist[k+curDy[p]][l+curDx[p]]
maxSum = max(sumOfSquare,maxSum)
print(maxSum)
가장 큰 loop로 도형을 선택하고 그 이후로는 모든 matrix의 요소들을 탐색하게 한다. 그리나서 rotation을 각 도형의 경우의 수에 따라 정한 만큼 순회하여 matrix의 범위 안에 도형이 들어온다면 합을 구해준다.
주의할 점
- 각각의 경우의 수가 너무 많기 때문에, 실수를 할 수 있으니 도형좌표를 찍을 때에 실수하지 않도록 주의하자.
- 메모리나 시간관리를 잘 해야한다. for문이 상당히 중첩이 될 수 있기 때문에 dx, dy와 같은 도형좌표를 저장하거나 그 이외 다른 정보들을 최대한 저장할 수 있는 방법을 찾아보자.
전체코드
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
maplist = []
for i in range(N):
maplist.append(list(map(int,input().split())))
dx = [[0,1,2,3],[0,1,0,1],[0,0,0,1],[0,0,1,1],[0,1,1,2]]
dy = [[0,0,0,0],[0,0,1,1],[0,1,2,2],[0,1,1,2],[0,0,1,0]]
convertedDx = [[0,-1,-2,-3],[0,-1,0,-1],[0,0,0,-1],[0,0,-1,-1],[0,-1,-1,-2]]
convertedDy = [[0,0,0,0],[0,0,-1,-1],[0,-1,-2,-2],[0,-1,-1,-2],[0,0,-1,0]]
rot = [[0,1],[0],[0,1,2,3,4,5,6,7],[0,1,4,5],[0,1,2,3]]
maxSum = 0
# cases of squares
for i in range(5):
# iterate map
for k in range(N):
for l in range(M):
# cases of rotation
for j in range(len(rot[i])):
curRot = rot[i][j]
curDx = []
curDy = []
if curRot == 0:
curDx = dx[i]
curDy = dy[i]
elif curRot == 1:
curDx = convertedDy[i]
curDy = dx[i]
elif curRot == 2:
curDx = convertedDx[i]
curDy = convertedDy[i]
elif curRot == 3:
curDx = dy[i]
curDy = convertedDx[i]
elif curRot == 4:
curDx = dx[i]
curDy = convertedDy[i]
elif curRot == 5:
curDx = convertedDy[i]
curDy = convertedDx[i]
elif curRot == 6:
curDx = convertedDx[i]
curDy = dy[i]
elif curRot == 7:
curDx = dy[i]
curDy = dx[i]
if l+max(curDx) < M and k+max(curDy) < N and l+min(curDx) >=0 and k+min(curDy) >= 0:
sumOfSquare = 0
for p in range(4):
sumOfSquare+=maplist[k+curDy[p]][l+curDx[p]]
maxSum = max(sumOfSquare,maxSum)
print(maxSum)