인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

전체적으로 좋은 코드네요 ㅎㅎ

다만,

    for(int i = 0; i < 4; i++){
        int ny = y + dy[i] * (adj[y][x] - '0');
        int nx = x + dx[i] * (adj[y][x] - '0');

        temp = max(temp,algo(ny,nx, cnt + 1));
    }

코드를 보면 이런식으로 매개변수에 DP에 넣어주고 있는데요.

이 경우 부분 최적해가 올바르게 쌓이지 못합니다.

예를 들어 a -> b -> c -> d라고 했을 때 a, b, c, d 의 DP 모두 4가 되어버리는 문제점이 생기는 것이죠.

예를 하나 더 들어볼까요?

입력

3 7

3942178

1234567

9123532

옳지 않은 DP : 지금의 수강생님 코드

5 3 0 5 0 3 5

0 0 0 0 0 0 0

4 0 0 5 5 0 5

5

입력

3 7

3942178

1234567

9123532

옳은 DP : 해답 코드

5

5 1 0 4 0 1 1

0 0 0 0 0 0 0

1 0 0 3 1 0 2

즉, 이런식으로 DP가 올바르게 쌓이지 않기 때문에 틀리게 됩니다.

부분최적해를 올바르게 이용해서 전체최적해를 쌓아가서 답을 만들어야 하는데 부분최적해를 이용할 때 그 때의 해가 이상하게 있기 때문에 이를 기반으로 전체해를 구할 때 UB가 발생할 수 있는 것이죠.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.