제가 코드를 제대로 해석하지 못한 걸 수도 있는데 이 코드로는
넣음=O, 안 넣음=X일 때
OXXOXOOXXOXOO
같은 건 처리 못 하고
XXXOOOOOXXXX
같은 것만 처리할 수 있는 거 아닌가요?
1450번 - 냅색문제
제가 코드를 제대로 해석하지 못한 걸 수도 있는데 이 코드로는
넣음=O, 안 넣음=X일 때
OXXOXOOXXOXOO
같은 건 처리 못 하고
XXXOOOOOXXXX
같은 것만 처리할 수 있는 거 아닌가요?
OXXOXOOXXOXOO같은 경우는 left=0,right=마지막일 때, 어차피 다 가방안에 들어간다면
총n개 중에 1개,2 개, 3개 해서 nC1+nC2+....이런 느낌으로 총 2^n으로 처리할 수 있을 것 같았습니다..!!
저도 고등학교 때 배운 이항정리 생각나서 써봤는데 마지막 문항 예시도 통과했습니다
일단 반례는 이거이긴 합니다. 가능한 모든 경우의 수 2^30에서 모두 선택하는 경우인 1가지를 뺀 1073741823이 정답인데 805306368이 나오네요.
여전히 원 코드가 뭘 의도한 건지도 여기서 이항 정리가 왜 나오는지도 모르겠는데 이건 중요한 게 아니니 생략하고 3~5 구간에서 센 개수랑 4~6 구간에서 센 개수를 중복 카운팅하는 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
namoo991026 1년 전
안녕하세요
23~25번째 줄에서 어차피 left랑 right랑 모두 만족한다면 그 안의 부분집합은 모두 만족한다고 생각하여
저렇게 2의 n승으로 더해서 풀었는데 예제는 모두 통과했습니다
그러나 답이 틀리다하여 혹시 논리상으로 이상한 부분이 있다면 알려주시면 감사하겠습니다
감사합니다