n×n크기의 격자 정보가 주어졌을 때, (1, 1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (n,n)으로 간다고 했을 때 거쳐간 위치에 적혀있는 수들 중 |최댓값-최솟값|을 최소로 만드는 프로그램을 작성해보세요.
예로 다음 그림을 살펴봅시다
입력 형식
첫 번째 줄에는n이 주어집니다. 두 번째 줄부터n개의 줄에 걸쳐 각 행에 해당하는n개의 정수 값이 공백을 사이에 두고 주어집니다.
1 ≤n≤ 100
1 ≤ 주어지는 숫자 ≤ 100
출력 형식
가능한 경로상의 |최댓값-최솟값| 중 최솟값을 출력합니다.
입출력 예제
예제1
입력:
3 1 2 3 5 4 6 7 1 2
출력:
3
예제2
입력:
4 20 30 51 30 22 10 12 1 10 25 35 21 34 36 20 20
출력:
21
백트래킹으로 풀었더니 예제는 맞는데 결국 시간초과가 발생한다.
import sys
sys.stdin=open('input.txt')
def in_range(nx,ny):
return 0<=nx<n and 0<=ny<n
dxs=[0,1]
dys=[1,0]
def DFS(x,y):
global ans
if x==n-1 and y==n-1:
ans = min(ans, abs(max(res)-min(res)))
return ans
for dx,dy in zip(dxs,dys):
nx=x+dx
ny=y+dy
if in_range(nx,ny) and dp[nx][ny]==0:
dp[nx][ny]=1
res.append(board[nx][ny])
DFS(nx,ny)
dp[nx][ny]=0
res.pop()
if __name__=="__main__":
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dp=[[0]*n for _ in range(n)]
dp[0][0] = board[0][0]
ans=sys.maxsize
res=[board[0][0]]
DFS(0,0)
print(ans)
'''
재귀 호출을 통해 중복된 계산이 발생하는 문제 발생
'''
결국 DP로 풀어야한다.
import sys
def check():
d = [[1e9]*n for _ in range(n)]
d[0][0] = board[0][0]
for j in range(1, n):
d[0][j] = max(d[0][j-1], board[0][j])
for i in range(1, n):
d[i][0] = max(d[i-1][0], board[i][0])
for i in range(1, n):
for j in range(1, n):
d[i][j] = max(min(d[i-1][j], d[i][j-1]), board[i][j])
return d[n-1][n-1] # 1e9면 경로 없음!
if __name__=="__main__":
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
INT_MAX=sys.maxsize
res = INT_MAX # |최대-최소|의 최소!
for low in range(1, 101):
for i in range(n):
for j in range(n):
if board[i][j] < low:
board[i][j] = INT_MAX
ans = check()
if ans < INT_MAX:
res = min(res, abs(ans-low))
print(res)
풀이
이 문제는 해설을 보고도 이해하기가 까다로운 문제였다.
핵심은 마스킹 기법을 이해하는 것이라고 봐도 무방하다.
DP 테이블 내의 원소는 최대 중에서도 최소를 골라 최종 최댓값만을 저장한다.
max(min(d[i-1][j], d[i][j-1]), board[i][j])
이 문제는 원소가 1부터 100까지의 값으로 매우 작기 때문에, 그 사이에 존재하는 모든 값을 최솟값(low)으로 지정하여 탐색을 진행한다.
만약 board 내에 최솟값low가 없다고 하더라도,작은 값부터모든 후보를 탐색하다 보면 가능한 값이 무조건 하나쯤은 존재하여 무시할 수 있게 된다.
한 경로의 최솟값은 무조건low여야 하므로 graph 내에low보다 작은 값이 있다면1e9값으로 마스킹 해준다.
최소라고 놓은 최솟값(low)이 실제 경로에서는 최소가 아니라면 가능한 경우의 수가d[n-1][n-1]에 기록되지 않을 것이라는 것을 의미한다.
d[n-1][n-1]값을 확인하여 이 값이1e9로 기록되어 있을 경우 가능한 경로가 없다는 것을 의미하므로 continue 한다.
마지막으로 |d[n-1][n-1]값에 기록된 최소 최댓값 - 실제 최솟값low|이"최소"가 되도록 하는res값을 업데이트하여 마무리한다.