격자 안에서 완전 탐색 알고리즘 문제를 풀어보자.
문제
n * m크기의 이차원 영역의 각 위치에 자연수가 하나씩 적혀있습니다. 이 때 아래의 그림에 주어진 2가지 종류의 블럭 중 한 개를 블럭이 격자를 벗어나지 않도록 적당히 올려놓아 블럭이 놓인 칸 안에 적힌 숫자의 합이 최대가 될 때의 결과를 출력하는 프로그램을 작성해보세요. 단, 주어진 블럭은 자유롭게 회전하거나 뒤집을 수 있습니다.
입력 형식
첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두 번째 줄부터 (n+1)번째 줄까지는 각 행의 숫자가 공백을 사이에 두고 주어집니다.
3 ≤ n, m ≤ 200
1 ≤ 자연수 ≤ 1,000
출력 형식
블럭 안에 적힌 숫자합의 최대값을 출력합니다.
입출력 예제
예제
입력
1
2
3
4
3 3
1 2 3
3 2 1
3 1 1
출력
1
8
내가 푼 풀이 코드
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
n,m = map(int,input().split(" "))
arr = [list(map(int, input().split())) for _ in range(n)]
max_sum =[]
# ㄴ자
max_val = 0
for i in range(n-1):
for j in range(m-1):
if max_val < arr[i][j]+arr[i+1][j]+arr[i+1][j+1]:
max_val = arr[i][j]+arr[i+1][j]+arr[i+1][j+1]
max_sum.append(max_val)
# ㅡl자
max_val = 0
for i in range(n-1):
for j in range(m-1):
if max_val < arr[i][j+1]+arr[i+1][j]+arr[i+1][j+1]:
max_val = arr[i][j+1]+arr[i+1][j]+arr[i+1][j+1]
max_sum.append(max_val)
# ㅣ-자
max_val = 0
for i in range (n-1):
for j in range (m-1):
if max_val < arr[i][j]+arr[i][j+1]+arr[i+1][j]:
max_val = arr[i][j]+arr[i][j+1]+arr[i+1][j]
max_sum.append(max_val)
# ㄱ자
max_val = 0
for i in range(n-1):
for j in range (m-1):
if max_val < arr[i][j]+arr[i][j+1]+arr[i+1][j+1]:
max_val = arr[i][j]+arr[i][j+1]+arr[i+1][j+1]
max_sum.append(max_val)
# ---자
max_val = 0
for i in range(n):
for j in range (m-2):
if max_val < arr[i][j]+arr[i][j+1]+arr[i][j+2]:
max_val = arr[i][j]+arr[i][j+1]+arr[i][j+2]
max_sum.append(max_val)
# ㅣ자
max_val = 0
for i in range(n-2):
for j in range (m):
if max_val < arr[i][j]+arr[i+1][j]+arr[i+2][j]:
max_val = arr[i][j]+arr[i+1][j]+arr[i+2][j]
max_sum.append(max_val)
print(max(max_sum))
수행 시간 : 135ms/ 메모리 : 25mb
- 시간복잡도는 O(nm) : 이중 반복문을 통한 리스트 탐색 + 기본 연산 + 비교연산
풀이 해설 : 내가 생각한 풀이 방법은 블럭의 회전 경우의 수를 그대로 나열해 각 최대값을 max_sum 리스트에 저장하고 max_sum 리스트에서 최대값이 정답이라고 생각했다.
느낀점
만약 가변 길이 블럭이 아니고 블럭이 모양이 고정되어있다면 DP(Dynamic Programming)방식을 이용해 풀 수 있었을 것이라 생각한다.