[일반] 바이너리 플립은 제발 100원짜리 동전을 뒤집어봐

[시아닌(kimjg1119)]

위치에 관한 제약조건이 없다는건 개수만 갖고 이래저래하면 된다는거잖아
직접 뒤집어보면 이해될거임

핫하 죽어라

[익명(110.11)]

프갤애 갖다줘보니까 다 이해 못함. 다 님같은 천재가 아니에여

[시아닌(kimjg1119)]

ㄴ그건 프갤이 좀...

[0xrgb(0xrgb)]

프갤에서 이거 이해할만한 사람은 다 여기옴

[0xrgb(0xrgb)]

그러니 여기서 답 안달리면 프갤가도 의미없을거임. 차라리 백준 게시판이나 슬랙 같은데 올리면 더 나을것

[시아닌(kimjg1119)]

바이너리 플립이 이해 안되면 bfs에 대한 기초적인 이해가 없는거. 공부하자...

[익명(110.11)]

ㄴ 아니 bfs를 통한 로직 코드는 이해가는데 수학적으로 짜는 로직이 이해 안간다니깐;

[시아닌(kimjg1119)]

ㄴ 최대 뒤집는 횟수는 a+b번 미만일거니까 모든 경우를 다 해보면서 하는거. 파라메트릭 서치의 하위호환이라고 생각하면 됨

[시아닌(kimjg1119)]

rest가 2의 배수여야 하는 이유는 당연히 0을 1로 모두 만들고 나서 그 상태를 유지하려면 남은 동전을 2번 단위로 뒤집어야 하기 때문

[시아닌(kimjg1119)]

근데 여기서 문제가 되는게 뭐냐면 한 동전은 0일때/1일때 최대 (i-1)/2 or i/2번밖에 원 상태로 유지하는 동작을 하지 못함

[시아닌(kimjg1119)]

왜냐면 총 i번 뒤집을건데 그럼 한 동전을 최대 i번밖에 뒤집지 못하자너

[시아닌(kimjg1119)]

그래서 use가 rest보다 커야되고, 내가 말한게 각각 2번 조건과 3번 조건임. 갓잇?

[dd(110.11)]

아 rest는 나머지 A를 제외한 나머지 뒤집는 횟수인데, 당연히 걔네는 한번 뒤집었다 다시 뒤집어야 한다(2번). 왜냐면 그래야 1되니까. 고로 짝수여야 된다는 거고

[시아닌(kimjg1119)]

ㅇㅇ

[dd(110.11)]

i 번 턴에서 총 i*k만큼 뒤집을 건데 그러면 한 동전을 최대 i번 만큼 뒤집을 수 있다. -> ...

[dd(110.11)]

3번 조건은 아직 명확히 이해가 안간다;;

[dd(110.11)]

아 근데 2번은 진짜 너가 설명한 게 훨씬 더 잘 이해되네. 너가 책 써도 될 듯

[익명(110.11)]

아 3번 조건 이거임??

[익명(110.11)]

한 동전은 0일때/1일때 최대 (i-1)/2 or i/2번밖에 원 상태로 유지하는 동작을 하지 못함 -> use

[익명(110.11)]

a를 제외한 나머지 뒤집는 횟수 rest보다 당연히 use가 커야되는 이유는 use는 a도 포함해서 뒤집으니까

[익명(110.11)]

고로 use >= rest