namoo991026   1년 전

안녕하세요

23~25번째 줄에서 어차피 left랑 right랑 모두 만족한다면 그 안의 부분집합은 모두 만족한다고 생각하여

저렇게 2의 n승으로 더해서 풀었는데 예제는 모두 통과했습니다

그러나 답이 틀리다하여 혹시 논리상으로 이상한 부분이 있다면 알려주시면 감사하겠습니다

감사합니다

leeingyun96   1년 전

제가 코드를 제대로 해석하지 못한 걸 수도 있는데 이 코드로는

넣음=O, 안 넣음=X일 때

OXXOXOOXXOXOO

같은 건 처리 못 하고

XXXOOOOOXXXX

같은 것만 처리할 수 있는 거 아닌가요?

namoo991026   1년 전


@leeingyun96님 안녕하세요!

OXXOXOOXXOXOO같은 경우는 left=0,right=마지막일 때, 어차피 다 가방안에 들어간다면

총n개 중에 1개,2 개, 3개 해서 nC1+nC2+....이런 느낌으로 총 2^n으로 처리할 수 있을 것 같았습니다..!!

저도 고등학교 때 배운 이항정리 생각나서 써봤는데 마지막 문항 예시도 통과했습니다

leeingyun96   1년 전

일단 반례는 이거이긴 합니다. 가능한 모든 경우의 수 2^30에서 모두 선택하는 경우인 1가지를 뺀 1073741823이 정답인데 805306368이 나오네요.

 

여전히 원 코드가 뭘 의도한 건지도 여기서 이항 정리가 왜 나오는지도 모르겠는데 이건 중요한 게 아니니 생략하고 3~5 구간에서 센 개수랑 4~6 구간에서 센 개수를 중복 카운팅하는 것 같습니다. 

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