[일반] F어캐푸는거임ㅁ

[dyp(irc2265)]

왜 다들 e얘기밖에 업지

[대학원오지마세요(publfl)]

m이 있으면 m을 2^t랑 m-2^t부분으로 잘 쪼갤 수 있음. 그러면 쪼갠걸 또 쪼개고 하다보면 divide and conquer가 되고 그거 걍 하면 됨. 시간은 약 60^2정도 나올겨

[익명(147.47)]

고수 - dc App

[dyp(irc2265)]

쪼갠걸 처리하는 방법을 모르겟음

[대학원오지마세요(publfl)]

m-2^t부분은 재귀적으로 또 쪼갤 수 있으니 그냥 2^t개를 어떻게 보는지만 설명하겠음. 2^t는 2^(t-1)과 2^(t-1)로 나눌 수 있고, 얘내를 잘 보면 뒤에 t-1번째 bit가 정확히 딱 1번씩 늘어나는걸 볼 수 있음. 그래서 뒤에 t-1개의 숫자와 나머지 앞에 숫자를 보면, 제일 처음에 앞에 숫자의 bit차이, 그리고 t-1번째 값이 정확히 1 늘어난뒤 자릿수올림해주고 나서 bit차이를 보면 이건 DP처럼 된다는걸 볼 수 있음. 이걸 힘껏 노가다

[dyp(irc2265)]