문제
[정수 사각형 최대 합]
풀러 가기
N* N 행렬이 주어졌을 때, (1, 1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N, N)으로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자의 합을 최대로 하는 프로그램을 작성해보세요.
입력 형식
첫째 줄에는 N이 주어집니다.
두 번째 줄 부터 N개의 줄에 각각 각 행에 해당하는 N개의 정수 값이 공백을 사이에 두고 주어집니다.
-
1 ≤ N ≤ 100
-
1 ≤ 행렬에 주어지는 숫자 ≤ 1,000,000
출력 형식
가능한 최대 합을 출력합니다.
Constraints:
시간 제한: 1000ms
메모리 제한: 80MB
입출력 예제
입력:
3
1 2 3
3 2 1
4 2 1
출력:
11
입력:
3
1 3 2
3 4 5
4 2 1
출력:
14
예제 설명
첫 번째 예제의 경우 다음과 같이 이동하면 합이 11이 되며, 더 좋은 답은 존재하지 않습니다 
풀이
Backtracking
backtracking과정에서 전역변수에 갱신해주는 방식의 함수 사용
탐색 가능한 모든 위치를 방문하며 도착점에 도달했을 떄 최대 합의 값을 갱신
🚫 시간이 오래걸려서 통과가 안 될 것이다
풀이과정
시작점 (0.0)부터 시작하여 방문 가능한 모든 위치를 탐색(도착점은 (N-1,N-1))
탐색방향인 아래, 오른쪽 방향에 대해 격자 내에 위치하면 각 위치로 이동하여 탐색
아래방향과 오른쪽 방향만 이동이 가능하므로 dx dy 테크닉을 이용하여 주어진 방향으로만 탐색
- 아래 방향: D
- 오른쪽 방향: R
코드
n = int(input())
grid = [
list(map(int, input().split()))
for _ in range(n)
]
max_sum = 0
def in_range(x, y):
return 0 <= x and x < n and 0 <= y and y < n
def find_max_sum(x, y, sum):
global max_sum
# 도착 지점에 도착하면 최대 합을 갱신해줍니다.
if x == n - 1 and y == n - 1:
max_sum = max(max_sum, sum)
return
dxs, dys = [1, 0], [0, 1]
# 가능한 모든 방향에 대해 탐색해줍니다.
for dx, dy in zip(dxs, dys):
new_x, new_y = x + dx, y + dy
if in_range(new_x, new_y):
find_max_sum(new_x, new_y, sum + grid[new_x][new_y])
find_max_sum(0, 0, grid[0][0])
print(max_sum)
결과
흑… 역시 안된다!!
DP (Tabulation)
동일한 상태를 정의하기 위한 요소
- 시작점에서 출발하려 마지막으로 방문한 위치
- 선택된 경로의 숫자 합
➡ 문제에서 최대 합을 구하라고 하였으므로 ‘시작점에서 출발하여 마지막으로 방문한 위치’ 가 동일한 경우,
‘선택된 경로의 숫자 합’ 이 최대가 되어야 한다
0) 입력값 받기
👀 코드 보기
# 입력값
n = int(input())
num = [
list(map(int, input().split()))
for _ in range(n)
]
# 기록할 것
dp = [
[0 for _ in range(n)]
for _ in range(n)
]
1) 격자 내 탐색
시작점에서 출발하여 마지막으로 방문한 위치가 동일한 상황에서,
1️⃣ 해당 위치까지 이동한 경로에 적힌 숫자들의 합의 경로의 전단계에서 방문한 노드(아래로 이동하기 전, 오른쪽으로 이동하기 전) 확인
- 바로 전 노드에서 아래 방향으로 이동하여 (i,j)로 오게 된 경우
- 이 경우 전 노드까지의 합인 dp[i-1][j] 에 이동 후의 수인 num[i][j]를 더해주면 된다.
- 바로 전 노드에서 오른쪽 방향으로 이동하여 (i,j)로 오게 된 경우
- 이 경우 전 노드까지의 합인 dp[i][j-1] 에 이동 후의 수인 num[i][j]를 더해주면 된다.
2️⃣ 이 노드 중에서 더 큰 값을 선택
dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) + num[i][j]
1.5) 끝 행 처리
[최좌측 열 처리]
전 행이 오른쪽 방향 에서 내려온 게 없음
전 행이 아래 방향 에서 왔다는 것만 생각해주면 된다
dp[i][0] = dp[i-1][0] + num[i][0] 로 값을 채워주면 된다
👀 코드 보기
# 최좌측 열의 초기값을 설정해줍니다.
for i in range(1, n):
dp[i][0] = dp[i-1][0] + num[i][0]
[최상단 행 처리]
전 행이 아래 방향 에서 내려온 게 없음
전 행이 오른쪽 방향 에서 왔다는 것만 생각해주면 된다
dp[0][j] = dp[0][j-1] + num[0][j] 로 값을 채워주면 된다
👀 코드 보기
# 최상단 행의 초기값을 설정해줍니다.
for j in range(1, n):
dp[0][j] = dp[0][j-1] + num[0][j]
최대 합 구하기
격자 내 모든원소에 대한 탐색이 끝난 후,
dp[N-1][N-1] 값: (0,0) 에서 시작해 (N-1,N-1)까지 도달할 떄의 최대합이 들어있게 됨 ➡ 해당 값을 출력해주면 된다
👀 코드 보기
# 탐색하는 위치의 위에 값과 좌측 값 중에 큰 값에
# 해당 위치의 숫자를 더해줍니다.
for i in range(1, n):
for j in range(1, n):
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + num[i][j]
print(dp[n-1][n-1])
전 노드가 더 큰 곳에서 화살표를 보냈다
코드
n = int(input())
num = [
list(map(int, input().split()))
for _ in range(n)
]
dp = [
[0 for _ in range(n)]
for _ in range(n)
]
def initialize():
# 시작점의 경우 dp[0][0] = num[0][0]으로 초기값을 설정해줍니다
dp[0][0] = num[0][0]
# 최좌측 열의 초기값을 설정해줍니다.
for i in range(1, n):
dp[i][0] = dp[i-1][0] + num[i][0]
# 최상단 행의 초기값을 설정해줍니다.
for j in range(1, n):
dp[0][j] = dp[0][j-1] + num[0][j]
# 초기값 설정
initialize()
# 탐색하는 위치의 위에 값과 좌측 값 중에 큰 값에
# 해당 위치의 숫자를 더해줍니다.
for i in range(1, n):
for j in range(1, n):
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + num[i][j]
print(dp[n-1][n-1])
결과
쨔쨘