[일반] F 풀이

[ㅁ(119.202)]

답은 [log_k(n)]임

여기서 [x]는 x보다 같거나 큰 가장 작은 정수

왠지는 몰?루

이렇게 푼사람들 주위에 많은데 나도 이렇게 풀었고

그런데 나도 왜 이게 되는지 모르고 주위에 이렇게 푼사람들도 모르고 전부 기도메타 하고있음

기도하는 사람이 이렇게나 많은데 맞지 않겠음?

proof by 집단지성

[캐티(tae826)]

Wrong answer on test 37

[ㅁ(119.202)]

안돼

[익명(180.231)]

아 어쩐지 그럴거같더라!!!! 뭔가 log와 관련이 잇을거같앗어 근데 알았어도 복원 방법을 몰라서 몰?루

[ㅁ(119.202)]

1번~ k번 정점 사이를 전부 1번색으로 칠하고, k+1~2k번 사이를 전부 1번색으로 칠하고... 이런식으로 함. 그뒤에 1~k를 1묶음, k+1~2k를 2묶음... 이런식으로 정의하면, 그다음은 1묶음~k묶음 사이를 2번색으로 칠하고, k+1묶음 ~ 2k묶음 사이를 2번색으로 칠하고, 또 이렇게 해서 k묶음을 다시 1묶음으로 생각함. 무한히 반복

[익명(180.231)]

이게 복원방법인거지?? log인거 증명이 아니라

[ㅁ(119.202)]

ㅇㅇ 그리고 이렇게하면 [log_k(n)]번만에 가능하긴 한데 실제 [log_k(n)]번이 답인지는 몰?루

[익명(180.231)]

그 뭔가 백준 트리dp 문제중에 답 상한이 log2N인 문제 있었는데 색칠하는문제인데 그거랑 아이디어 비슷한듯

[익명(180.231)]

근왜태그 비트마스크