3개의 댓글이 있습니다.
-
-
innocentchris -
조언 감사드립니다. 하지만 저는 모든 가능한 조합을 모두 탐색했다고 생각했습니다.
예를들면 첫번재 음식의 경우 뒤로 들어오는 모든 음식과의 조합을 다 탐색하게 됩니다.혹시 어떠한 부분에서 제가 놓쳤는지 조금더 지적해주시면 도움이 많이 되겠습니다.
9년 전 link
-
-
-
wafter -
같은 문제를 푼 사람입니다. 본 문제풀이에 어려움을 겪으시는 것 같아서 (저도 실력이 많이 없지만) 도움을 드릴 수 있을까 하여 위의 소스를 대강 분석해 보았습니다. 코드를 완전히 분석한 것은 아니지만, 프로그램의 로직의 오류를 두가지 정도 발견한 것 같습니다.
첫째는, 이미 CurrentSum이 goal을 이룬 것은 고려하지 않는 것입니다. goal을 이루었다 해도 새로 들어오는 음식이 많은 친구들을 커버할 경우 goal을 이루는데 필요한 음식의 개수는 더 적어질 수 있습니다.
둘째는, 현재 음식 정보를 stack에 쌓인 값하고만 비교한다는 것입니다. stack 에 쌓인 값 뿐 아니라 num 값도 비교해야 합니다. 그런데, 간혹 num이 불필요한 경우도 있을 수 있는데, 현재의 로직은 num값을 기준으로 한 상대적 값(증가분)을 stack에 저장하므로 num이 불필요한 경우는 처리하기가 매우 곤란해집니다. 프로그램을 수정해야 할 것 같습니다.
반례를 아주 간단한 걸로 들어 드리겠습니다.
[1] 친구 5명, 음식 5개
5 5
a b c d e
2 a b
2 b c
1 d
1 e
3 c d e
정답은 2 이지만 위의 코드는 4를 출력합니다.
[2] 친구 2명, 음식 2개
a b
1 a
2 a b
정답은 1 이지만 위의 코드는 2을 출력합니다.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
innocentchris
개인적으로 몇번이나 테스트 케이스를 만들어서 돌려봐도 정답이나 제출만 하면 계속 오답이 나와서 여쭈어보게 되었습니다.
꼭 부탁드립니다. 안되는 테스트케이스가 있으면 그것만이라도 보여주십시오.
알고리즘은 대략적으로 먹는 아이들을 비트로 만든후
각 음식을 최소로 중첩해서 모든 아이들을 먹일수 있게 하는 알고리즘입니다.
예를들어 a b c d가 있다고 하면 비트는 1111(2)=15, 즉 15가 최종 목표입니다.
음식이 1.(a b),2.(b c),3.(c d)라면
1.(a,b)=0011 =3
2.(b,c)=0110=6
3.(c,d)=1100=12
입니다.
여기서 1번에 3번을 쌓으면 15가 되어 완성중 하나로 취급합니다.
쌓는 과정은 이렇습니다.
1번에 2번을 쌓을경우 0100이 새롭게 추가되어 0111이 됩니다.3번을 추가할경우 1000이 추가되어 1111이 되어 비트가 완성됩니다. 다만 이 과정에서 3번(1100)은 쌓여있는 0100(새로운 비트만) 을 완벽히 포함하고 있기에 3번을 쌓고 2번을 버립니다. 따라서 총 스택은 2번입니다.
이런식으로 가장 최소로 쌓아 목표를 달성한 음식물을 제출합니다.
코드를 첨부합니다..
9년 전