DP질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

작성

259

안녕하세요 선생님 항상 에너지 넘치는 강의를 제공해주셔서 감사합니다.

DP문제를 푼 코드를 보았을 때 DP자료구조에 처음에 -1로 초기화한 이후 언제 dp자료구조의 값이 다른 값으로 저장 되는지 모르겠습니다.

답변 1

지식공유자

안녕하세요 noah님ㅎㅎ

DP문제를 푼 코드를 보았을 때 DP자료구조에 처음에 -1로 초기화한 이후 언제 dp자료구조의 값이 다른 값으로 저장 되는지 모르겠습니다.

>> 이 때 값이 저장이 됩니다.

    ret = INF;

처음 INF로 할당.

마지막 리프 노드의 재귀함수에서 (마지막 끝의 재귀함수)

    if(visited == (1 << n) - 1){
        return dist[here][0] ? dist[here][0] : INF;
    }

dist 등이 할당.

이런 것들이 쌓이면서 min값들이 할당.

        ret = min(ret, dist[here][i] + tsp(i, visited | (1 << i)));

초기 할당된 INF가 변경되면서 ret이 -1이 아닌 다른 값으로 할당이 됩니다.

감사합니다.

질문자

int &ret = dp[idx][turn] 여기에서 ret의 값이 변경되면 dp배열의 값이 변경 되는 건가요??

지식공유자

네 맞습니다.

ret에다가 reference로 값을 할당했기 때문에 ret이 수정되면 해당 배열도 수정이 됩니다. (같은 주소값을 공유하므로.)

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