⭐⭐⭐⭐[코드트리] [학습하기] [시뮬레이션] 기울어진 직사각형

https://www.codetree.ai/missions/2/problems/slanted-rectangle/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 

1이상 100이하의 숫자로만 이루어져 있는 n * n 크기의 격자 정보가 주어집니다.

이때, 이 격자 내에 있는 기울어진 직사각형들을 살펴보려고 합니다.

기울어진 직사각형이란, 격자내에 있는 한 지점으로부터 체스의 비숍처럼 대각선으로 움직이며 반시계 순회를 했을 때 지나왔던 지점들의 집합을 일컫습니다. 이 때 반드시 아래에서 시작해서 1, 2, 3, 4번 방향순으로 순회해야하며 각 방향으로 최소 1번은 움직여야 합니다. 또한, 이동하는 도중 격자 밖으로 넘어가서는 안됩니다.

 

예를 들어 위의 규칙에 따라 다음과 같은 기울어진 직사각형을 2개 만들어 볼 수 있습니다.

가능한 기울어진 직사각형들 중 해당 직사각형을 이루는 지점에 적힌 숫자들의 합이 최대가 되도록 하는 프로그램을 작성해보세요.

위의 예에서는 다음과 같이 기울어진 직사각형을 잡게 되었을 때 합이 21이 되어 최대가 됩니다.

 

입력 형식

첫 번째 줄에는 격자의 크기를 나타내는 n이 주어집니다.

두 번째 줄부터는 n개의 줄에 걸쳐 격자에 대한 정보가 주어집니다. 각 줄에는 각각의 행에 대한 정보가 주어지며, 이 정보는 1이상 100이하의 숫자로 각각 공백을 사이에 두고 주어집니다.

• 3 ≤ n ≤ 20

출력 형식

가능한 기울어진 직사각형들 중 최대의 합을 출력해주세요.

 

입출력 예제

예제1

입력:

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

 

출력:

21

 

---

처음에 BFS나 DFS로 풀어야하나 생각들었는데 해설을 보고 이거 다 싶은 정답 코드였다. 

외우고 익숙해지자

 

import sys


# 너비, 높이 모두 1일때 4개칸 순환
dxs=[-1,-1,1,1]
dys=[1,-1,-1,1]



def in_range(nx,ny):
    return 0<=nx<n and 0<=ny<n

def get_score(x,y,w,h):
    move_size=[w,h,w,h]
    
    total=0
    for dx,dy,length in zip(dxs,dys,move_size):
        for _ in range(length): # 처음 올라가는 대각선으로 length 만큼 옮겨봄 
            x = x+dx
            y = y+dy
            
            # 범위에 벗어나면 이 w,h에 대해서는 나가리니깐 
            # 그냥 바로 return 0으로 끝내줘 버림 
            if not in_range(x,y):
                return 0
            # 한칸 한칸 올라가면서 범위 안 벗어나면 더해주고 방향바꿔가며 시작지점까지 옴
            total += board[x][y]
    
    return total
            
    

if __name__=="__main__":
    n=int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    
    ans=0
    for i in range(n):          # 보드 범위, 보드 완전탐색 
        for j in range(n):
            # (i,j)일때 가능한 최대 너비(w)와 최대 높이(h)의 직사각형을 생각해보자 
            for w in range(1,n):
                for h in range(1,n):
                    #(i,j)를 시작으로 w너비와 h높이를 가지는 직사각형 점수
                    ans=max(ans, get_score(i,j,w,h))    
    
    print(ans)