minhas2   7년 전

저는 처음에 중복되는 숫자들을 생각하지 못하고 가장 최솟값을 가지는 원소를 탐색하고

그 원소에 해당하는 열과 이웃하는 행을 제외한 원솟값들 중 최솟값을 탐색하며

이 순서를 반복해서 결과값을 도출하는 식으로 생각했습니다.

그런데 중복되는 숫자가 있는경우를 생각해 봐야했었습니다.

그래서 중복되는 원소에 대해서는

방법 1)각각의 원소에 대해서 해당하는 열과 이웃하는 행을 제외한 원솟 값들을 모두 더하여 배열에 저장한다음,

가장작은값을 가지는 원소를 최솟값으로 할당해주는 방식으로 수정하였습니다.

그런데 이것도 아닌것 같더라고요..

방법 2)그래서 그 원소에 해당하는 열과 이웃하는 행의 값들의 합이 가장 큰 경우가 최솟값으로 선택하는 방식으로도 바꿔봤습니다. 근데 이것도 아니더군요..ㅎㅎ


중복하는 경우엔 어떤부분을 생각해봐야할지 감이 안잡힙니다

부탁드립니다 ㅜㅜ

소스에 주석처리된 부분은 방법 2에대한 부분이고

주석처리 밑에부분은 방법 1에대한 부분입니다.

zlzmsrhak   7년 전

일단 중복되는 수가 없어도 문제가 있는 알고리즘입니다. 동적계획법에 대해 더 알아보시는 것이 좋을 것 같습니다.

 반례입니다.

minhas2   7년 전

감사합니다. 왜 이렇게 간단한 반례경우는 생각못해본건지.. 다시 공부해보고 풀어보겠습니다 감사합니다!

댓글을 작성하려면 로그인해야 합니다.