아! 그리고 하나 더..
예제도 실험해보고, 제가 직접 예제 만들어서 해봤는데 안 되더라구요..
그리고 부분점수 못 받은 부분들이 시간초과 뜨는 데 어떻게 해야 할까요?
31963번 - 두 배
이 문제는 배열의 이전 값에 2배를 하는 식으로, 소위 '보이는 대로' 풀면 33점밖에 받을 수 없습니다.
d[i]를 실제로 변경하지 않고 '몇 번 2배를 해서 이전 수보다 크거나 같아졌는지'를 체크하는 별도의 배열을 만들어 보세요.
현재 수 d[i]에 대해, 이것이 이전 수, 즉 d[i - 1]를 2의 x제곱만큼 곱한 수 d[i] * 2x보다 크거나 같으려면 d[i]를 2의 y제곱만큼 곱해야 한다고 합시다.
그렇다면 다음의 식이 성립할 것입니다.
d[i - 1] * 2x <= d[i] * 2y
양변에 밑이 2인 로그를 씌우면
x + log2(d[i - 1]) <= y + log2(d[i])
우리는 y를 구하고 싶습니다. 이때 x는 제가 말씀드린 배열로 관리하고, d[i - 1]과 d[i]도 모두 아는 값이니
y >= x + log2(d[i - 1] / d[i])
이때 구한 y가 별도 배열의 i번 인덱스의 값이 됩니다. 그러면 다음 수 d[i + 1]에 대해서도 동일한 연산을 반복할 수 있습니다. 입력 배열을 순회하면서 모든 인덱스에 대해 y를 구해 더하면 됩니다.
추가적으로, overflow를 조심하세요.
댓글을 작성하려면 로그인해야 합니다.
tmaze 1년 전 1
어떤 부분이 왜 틀렸는지 알려주세요..!
몇 퍼센트에서 틀렸는지는 올리지 말라고 공지사항에 있어서 올리지 않을게여..
부분 점수 받았는데 나머지 점수를 못 받겠어요