구상은 잘했는데 비트마스킹에서 long으로 처리하는 과정에서 1<<zero로 넣다가 계속 틀려서 멘탈나가다가 겨우 풀어냈습니다 long인 변수로 비트마스킹할때는 항상 1L로 정해야 하는 걸 실수할줄은 몰랐네요
풀이과정을 설명드리자면 수를 1씩 늘려나가면서 B가 될때까지 1의 갯수를 세면 최대 10^16이기 때문에 시간초과가 나게 됩니다
그래서 제가 생각한 풀이는 101000이란 수를 110000으로 만들고 싶을 때 앞에 있는 3개의 0을 가지고 만들 수 있는 조합의 갯수를 생각했습니다
그러면 101000~101111까지 나오는 1의 갯수는 3C1*(1+2)+3C2*(2+2)+3C3*(3+2)개가 됩니다 여기서 더해지는 2는 101000이 원래 가지고 있는 1의 갯수 2개입니다
이렇게 구하면 8번 연산해야 나올 수 있는 1의 갯수를 3번만에 구할 수 있게 되겠네요 결과적으로 2^n번의 연산을 n번의 연산으로 줄일 수 있다고 생각했습니다
이 연산을 전부 끝낸 다음 101000을 101111로 만들어서 1을 더해준 후 110000에서 나오는 1의 갯수 2개를 더해주고 앞의 풀이를 수가 같아질 때까지 반복하는 방식으로 풀었습니다
101111로 만들어서 1을 더해주는 이유는 3개의 0이 전부 1이 된 상태에서 다음의 전체 1이 몇개가 될지는 알 수 없기 때문입니다 아마 더 메모이제이션을 써먹는다면 0이 0개일때 나오는 경우의 수~0이 53개일때 나오는 경우의 수까지도 다 메모해서 써먹을 수는 있겠네요
멘탈이 나가있는 상태였어서 거기까지 작성하진 않았고 좀 더 효율적으로 짜낸다면 diff메서드의 시작인덱스를 이전의 결과를 사용해서 더 줄일수도 있겠네요
그리고 이런 방식으로 풀어야 할 때 주의할 점이 35행의 조건문인데 이 조건문을 사용하지 않는다면 B가 110110이고 A가 110100일 때 A에서 110111까지 구해버리는 사고가 발생할 수 있습니다 따라서 가장 처음으로 달라지는 인덱스인 1로 바꿔준다면 정확한 연산으로 답을 낼 수 있습니다
lsk2343 1년 전 1
구상은 잘했는데 비트마스킹에서 long으로 처리하는 과정에서 1<<zero로 넣다가 계속 틀려서 멘탈나가다가 겨우 풀어냈습니다 long인 변수로 비트마스킹할때는 항상 1L로 정해야 하는 걸 실수할줄은 몰랐네요
풀이과정을 설명드리자면 수를 1씩 늘려나가면서 B가 될때까지 1의 갯수를 세면 최대 10^16이기 때문에 시간초과가 나게 됩니다
그래서 제가 생각한 풀이는 101000이란 수를 110000으로 만들고 싶을 때 앞에 있는 3개의 0을 가지고 만들 수 있는 조합의 갯수를 생각했습니다
그러면 101000~101111까지 나오는 1의 갯수는 3C1*(1+2)+3C2*(2+2)+3C3*(3+2)개가 됩니다 여기서 더해지는 2는 101000이 원래 가지고 있는 1의 갯수 2개입니다
이렇게 구하면 8번 연산해야 나올 수 있는 1의 갯수를 3번만에 구할 수 있게 되겠네요 결과적으로 2^n번의 연산을 n번의 연산으로 줄일 수 있다고 생각했습니다
이 연산을 전부 끝낸 다음 101000을 101111로 만들어서 1을 더해준 후 110000에서 나오는 1의 갯수 2개를 더해주고 앞의 풀이를 수가 같아질 때까지 반복하는 방식으로 풀었습니다
101111로 만들어서 1을 더해주는 이유는 3개의 0이 전부 1이 된 상태에서 다음의 전체 1이 몇개가 될지는 알 수 없기 때문입니다 아마 더 메모이제이션을 써먹는다면 0이 0개일때 나오는 경우의 수~0이 53개일때 나오는 경우의 수까지도 다 메모해서 써먹을 수는 있겠네요
멘탈이 나가있는 상태였어서 거기까지 작성하진 않았고 좀 더 효율적으로 짜낸다면 diff메서드의 시작인덱스를 이전의 결과를 사용해서 더 줄일수도 있겠네요
그리고 이런 방식으로 풀어야 할 때 주의할 점이 35행의 조건문인데 이 조건문을 사용하지 않는다면 B가 110110이고 A가 110100일 때 A에서 110111까지 구해버리는 사고가 발생할 수 있습니다 따라서 가장 처음으로 달라지는 인덱스인 1로 바꿔준다면 정확한 연산으로 답을 낼 수 있습니다