rdd6584   4년 전

1. 슬라이드에서 제시하는 풀이의 증명을 알 수 있을까요?

혹은 참고할만한 링크가 있나요?

2. 저는 맨 처음에 길이 3짜리로 그리디 하게 채우고,

그 다음 길이 2,

길이 1를 각각 채울 수 있을만큼 채우는 방법으로 했는데, 왜 제 알고리즘은 최적해를 찾지 못할까요?

도와주세요 ㅠㅠ

clrmt   4년 전

preview

일단 반례는 이렇습니다.

clrmt   4년 전

사실 위 반례가 이 그리디 문제의 유일한 형태의 반례입니다.

Greedy에 따라 블럭을 확장하는 것은 좋지만, 어떤 경우에 위의 케이스가 발생하는지 그 조건식만 세워주면 됩니다.

preview

저같은 경우는 1번 블럭에서부터 3, 2, 1의 순서대로 개수를 최대한으로 하고 나서, 이후에 2번 블럭이 3번 블럭보다 많을 때는

1번 블럭의 3칸짜리를 2칸짜리로 줄였습니다. 그렇게 하면 3번 블럭의 개수가 다시 생겨나기 때문에 2번에서부터 3번, 4번 블럭으로 연결할 수 있겠죠.

조건이 복잡해보이지만 간소화하니까 꽤나 간단해졌습니다.

rdd6584   4년 전

와 이런 반례를 생각하지 못하고 있었네요.

덕분에 이해갔습니다.

감사합니다.

yclock   4년 전

안녕하세요. 출제자 yclock 입니다.

대회 풀이 슬라이드에서 생략되어 있는 내용은, 저의 블로그 ( youngyojun.github.io )에서 자세하게 다루고 있습니다. (블로그 홍보 ><)

블로그의 "나는코더다 2019 송년대회 이야기" 글을 읽어주시면 감사하겠습니다. 증명 또한 담겨 있습니다.

감사합니다.

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