corona10   9달 전

테스트 케이스는 통과를 하는데 오답이라고 하네요. 지적부탁드립니다 

접근방법은 주석에 적었습니다..

amok   9달 전

반갑습니다. 같은 학교 다니네요.

접근 방법이 완전히 잘못되었습니다.

1
3 2
10 10 0 0 0
12 0 0 0 0
0 12 0 0 0

를 입력으로 넣어보세요.

총 K번의 각각의 선택마다 점수를 최대화하려 하는데, 동적 계획법보다는 그리디라고 할 만한 방법인 것 같네요. 

또 하나 보이는 문제점은 chosen[j] 를 true로 만든 후 이전에 true로 만들었던 chosen을 가만히 둔다는 것인데, 다음 입력을 넣어보세요. 이건 비교적 사소한 문제점인데, 이걸 고친다고 문제가 해결되는 것은 아닙니다만...

1
5 5
10 0 0 0 0
0 11 0 0 0
0 0 12 0 0
0 0 0 13 0
0 0 0 0 14



amok   9달 전

힌트를 드리자면, 예를 들어 N개의 장비 중에서 3개를 고른다고 할 때, 최종 장비의 합성 점수가 (a, b, c, d, e) 라고 합시다. 이 최종 합성 점수에서, a, b, c, d, e는 각각 적당한 장비의 점수였을 텐데, a는 10번 장비의 점수, b와 d는 89번 장비의 점수 c는 5번 장비의 점수, e는 65번 장비의 점수와 같이 되는 것은 불가능합니다. 우리는 장비 최대 3개를 합성했으니까요. a, b 는 45번 장비의 점수, c, d는 67번 장비의 점수, e는 90번 장비의 점수처럼 되는 경우는 가능합니다. 만약 우리가 a와 b가 같은 장비의 점수에서 나오는 것을 안다면, O(N)의 스캔으로 a+b을 최대화하는 장비를 알아낼 수 있겠죠.

구현이 상당히 까다롭습니다.

corona10   9달 전

amok님  주신 힌트로 다시 한번 문제 풀어봐야겠네요.  정말로 감사드립니다. 

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