문제해결기법 조교를 하며

이번에 과제로 https://www.acmicpc.net/problem/11048

해당 문제와 비슷한 문제가 나왔다, 차이가 있다면 최대가 아니라 최소라는 것

 

그래서 해당 문제에서 유의해야할 것은 두 가지 있다.

 

위 문제에서는 r+1,c+1을 이용할 필요가 전혀 없다. 음수인 값도 없기 때문에 r+1 -> c+1이나 c+1 -> r+1을 해서 손해를 볼 일이 없기 때문이다.

 

최소가 되도록 하기 위해서는 r+1과 c+1도 의미가 있다. 사실상 백준의 저 문제에서도 구현에서 r+1,c+1을 포함해도 문제가 없기 때문에 과제로 나온 문제에서 문제가 발생한 사람은 없었다.

 

다른 하나는 dp를 이용해 이 문제를 해결한다면 테두리의 값을 신경써야 한다. 보통 dp 테이블을 만들 때 n+1, m+1로 제작을 하는데 이 경우 테두리의 값을 별도로 초기화 하거나 배열 전체의 값을 별도로 초기화 시킬 필요가 없다.

이 테두리가 정답에 영향을 가게 만들어서는 안된다. 단순히 r-1, c-1을 하기 위해 index를 맞춰주기 위해 존재하는 것이지 dp 진행 중에 해당 테두리의 값이 영향을 주어서는 안된다.

 

최대를 찾는 문제에서 음수가 없으므로 0으로 초기화해준다면 문제가 없을 것이다. 그렇다면 최소에서는?

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
dp = [[0 for i in range(m+1)] for i in range(n+1)]

candy=[list(map(int, input().split())) for i in range(n)]

for i in range(1, n+1):
    for j in range(1,m+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + candy[i-1][j-1]

print(dp[-1][-1])

풀이를 올리면 위와 같다, 굳이 r-1,c-1을 탐색하지 않아도 되고, r=0 이나 c=0인 부분에 별도의 초기화가 필요하지 않다.

 

그러나 최소가 되려면 초기 배열을 적절히 큰 값으로 초기화를 해주거나 예외처리를 해줘야 한다. 특히 r=0이나 c=0인 부분에 대해서는 적절한 처리가 이루어져야 하는데

 

예를 들어 dp 테이블의 값을 적절히 초기화해주지 않는다면 아래와 같은 문제가 발생한다.

#dp 테이블
[0,  10, 10, 10]
[10, 0,  0,  0 ]
[10, 0,  0,  0 ]
[10, 0,  0,  0 ]

만약 위와 같이 초기화한 배열이 있고 입력이

6  10 10
6  10 10
0  0  0

이렇게 입력이 들어온다면

실제 정답은 12이다. 그렇지만 일반적으로 구현하는 방식대로 min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1]) + candy[i-1][j-1]을 하게 된다면

아래와 같은 위치를 탐색할 때 문제가 발생하게 된다.

#dp 테이블
[0,  10, 10, 10]
[10, 6,  16, 26]
[10, 12, 16, 26]
[10, X,  0,  0 ]

X를 탐색할 때 테두리의 10을 선택하게 된다. 따라서 최종 배열은 아래와 같게 된다.

#dp 테이블
[0,  10, 10, 10]
[10, 6,  16, 26]
[10, 12, 16, 26]
[10, 10, 10, 10]

따라서 테두리의 값을 적절히 큰 값으로 초기화를 해줘야 한다.

 

항상 위와 같은 상황이 주어졌을 때 적절히 큰 값의 기준을 잘 잡아주어야 한다.

예시를 든다면 매개변수탐색 진행 시 최소 최대의 값을 잡는 느낌으로