mojunseo49   4달 전

제출하여보았지만 틀렸다고 나와서 질문드립니다.

제가 머리가 나빠서 획기적인 알고리즘은 구현하지못하였고..

제 방법은 이렇습니다.

전제는 첫번째 입력된 집의 비용이 아닌, 전체에서 가장 적은 비용이 드는 집부터 골라 색칠합니다.

testcase를 예로 들면 26이 아닌, 13부터 찾게 됩니다.(문제 이해를 잘못한건가요?)

일단 배열에 입력된 비용들을 저장합니다.

첫번째로 전체에서 가장 적은 비용인 13을 찾아 내었고, 그 집은 13이 해당된 RED로 색칠하였기 때문에

더이상 행 정보는 필요하지 않습니다. 또, 이웃집은 RED로 칠할 수 없기 때문에 13이 저장된 열의 위 아래도 필요하지 않습니다.

따라서 배열의 해당위치는 0으로 바꿉니다.

두번째로 13 다음으로 작은 비용을 찾아내고, 위와 같은 방법으로 0으로 바꿉니다.

모든 집을 채우게되면 최소값을 리턴합니다.

아래는 Test case 결과입니다.

26 40 83 

0 60 57 

0 0 0 

------------------------
0 0 0 

0 60 57 

0 0 0 

-------------------
0 0 0 

0 0 0 

0 0 0 

-------------------
96


알고리즘 자체가 최소값을 구할 수 없다고 생각됩니다.

문제의 해답인 최소비용을 구하기 위해서는 최소 비용 뿐만 아니라, 그걸 선택함에 따른 감가상각도 고려를 해야합니다.

(이때문에 저도 다른 알고리즘을 짜봤지만 답이 틀리더군요...)


간단한 예제를 들어드리겠습니다. 

1    2     3

4 100 200

5    6     7

위의 경우, 눈으로 대충 봐도 답이 2, 4, 6순으로 선택해서 12임을 알수 있습니다.


하지만 님의 알고리즘 대로라면


1선택

0     0     0

0  100 200

5     6      7


5선택

0     0     0

0  100 200

0     0     0


100선택

0     0     0

0     0     0

0     0     0


답 : 106이 나오게 됩니다.

allkanet72   4달 전

전체 중에 최솟값을 먼저 칠하는 알고리즘은 그럴듯해 보이지만, 결과적으로는 최솟값이 안 나올 수 있습니다.
최솟값, 혹은 최댓값만 선택하는 것을 '탐욕적 알고리즘' 이라하는데 유의해서 사용해야합니다.
구글링을 하시면 많은 반례사례등을 얻으실 수 있습니다.

윗분의 사례처럼 
1    2     3
4 100 200
5    6     7

탐욕적으로 푼다면 무조건 1이 선택되죠. 1-100-5 결과적으로는 최악의 선택이 되는 겁니다.

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%...

위키백과에도 정확히 정의 되어있습니다.

"최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다." 라구요

mojunseo49   4달 전

저도 글을 쓰고나서 케이스를 여럿 만들어해봤는데, 고정적인 케이스에서만 최솟값이 나오더군요.

점화식 공부를하고 식을 세워서 더 풀어봐야할 것같아요!

댓글 감사합니다!

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