새소식

Computer Science/코딩테스트 문제 풀이

⭐⭐⭐⭐[코드트리] 정수 사각형 차이의 최소 2

  • -

문제 

 크기의 격자 정보가 주어졌을 때, (1, 1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (, )으로 간다고 했을 때 거쳐간 위치에 적혀있는 수들 중 |최댓값-최솟값|을 최소로 만드는 프로그램을 작성해보세요.

예로 다음 그림을 살펴봅시다

 

 

입력 형식 

 

첫 번째 줄에는 이 주어집니다.
두 번째 줄부터 개의 줄에 걸쳐 각 행에 해당하는 개의 정수 값이 공백을 사이에 두고 주어집니다.

  • 1 ≤  ≤ 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 값을 업데이트하여 마무리한다.

 

Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.