dannydino   4년 전

무작정 찾는 코드로 작성하니 반례도 있을뿐더러 시간초과가 뜹니다.

10의 18승까지의 입력을 받아서 최솟값을 계산해야하는데 어떻게 계산시간을 줄일 수 있을까요?

아이디어좀 부탁드립니다..

adh0463   4년 전

전 이렇게 접근했어요

1. 초기엔 감소 연산만 쓴다고 가정하고 답을 n-1로 갱신합니다.

2. 가까운 모든 자연수 제곱수를 a^b = k 꼴로 표현하고 각 자연수 제곱수에 대해서 결과에 |k - n|를 더해줍니다.

32. 다시 a를 n으로 생각하고 1. 연산을 재귀적으로 수행합니다.

참고 1) 단 무작위로 수행하면 시간 초과가 날 것이 뻔합니다. 마치 BFS처럼 떠돌게 됩니다.

참고 2) n에서 가까운 a^b에서 b가 고정된 상태에서 n에서 가장 가깝게 하는 값을 a1, a2(a1 <= a2, a2 - a1 <= 1)라고 하면 a2^b - a1^b < 2000000000을 만족합니다. 이 값을 가장 크게 하는 999999999과 1000000000를 직접 대입해보면 됩니다.

도움이 됐으면 하네요 :)

dannydino   4년 전

답변 달아주셔서 정말 감사합니다! 이해가안되는부분이 있어서그런데 질문 몇개만 더 해도될까요..?

1. 가까운 모든 자연수 제곱수를 찾을때 시간초과가 나지않나요? 이 부분도 적당히 규칙을정해서 검색할 a 범위를 정해주어야되나요?

2. 각 자연수 제곱수에 대한 결과에 |k-n| 을 더해주는 이유가 무엇인가요? 또한 더한 뒤 3번에서 a를 n으로 생각한다고 하셨는데 그럼 |k-n|을 더해준 제곱수값은 어디서 쓰이는것인가요?

adh0463   4년 전

N범위가 10^18이니 a^b에서 b의 최대값은 62가 됩니다. 가까운 모든 자연수 제곱수(b = [2, 62])를 모두 찾는다 하더라도 최대 61 x 2 = 122 개의 지점을 가지게 됩니다. 2를 곱하는 이유는 N을 기준으로 가까운 지점이 왼쪽 또는 오른쪽에 있을 수 있으니까 해준겁니다.

최대 122개의 점에 대해 N+x=k=a^b라고 쓴다면 N으로부터 1씩 이동하는 연산을 통해 이동할 필요가 있어요. 그래서 |x| = |a^b-N|=|k-N|이라고 표기한 거에요

시간초과 관련해서는 N->a^b까지 오면 a를 다시 N으로 봐서 a를 기준으로 가까운 모든 자연수 제곱수를 찾습니다. 기존 N의 수를 최소 루트(최대 62 루트)만큼 범위를 줄이게 됩니다.

마냥 재귀를 돌리면 똑같은 수를 계속 도는 경우가 발생하니 dp를 사용하시면 되겠습니다. 재귀를 사용 안하신다면 최단거리 알고리즘도 될 듯하네요~

dannydino   4년 전

설명해주신걸 바탕으로 이해한게..잘 정리가 안되는것같습니다 흑흑 ㅠㅠ

1. 2의 63승(계산기로 계산해보니까 2^63 = 9.22337203686e+18이더라구요)이 가장작은숫자중에 최대의 지수를 갖고있으니까 최대숫자를 입력받아도 2^63 -> 3^62(아니겠지만 예를들어) ->4^61 이런식으로 찾아본다는건가요?

2. |k-N|의 의미는 이해가되었는데 이걸 자연수 제곱수에 더하는 이유는 무엇인가요? 예를들어 1->2->16->17->289 의 경우에는 289가 17의 제곱이니 ..쓰다보니 이해가된것같기도하네요 ㅎ...

|k-N|을 자연수 제곱수에 더한다는 말씀이 N을 만드는 각 자연수제곱수의 횟수 정보에 추가한다는 말씀이신가요?

adh0463   4년 전

1. 네 그렇게 찾아가는 걸 말씀드린거에요. 오버플로우 힌트를 드리자면 log 함수를 써보세요. 하지만 double 오차에 대해서 처리할 필요가 있어요

조금 더 힌트를 드리자면, a^b, b=[2, 62]에서 각 정수 b(2, 3, 4, ..., 62)에 대해 a가 가질 수 있는 최대값을 이분탐색으로 구했습니다(a가 가질 수 있는 최소값은 당연히 2겟죠 ?).

여기서 각 b에 대해 N과 가장 가까운 제곱수(a^b)를 이분탐색으로 구했습니다.

2. 네 맞습니다. 만약 N=292이라면 292에서 289(17^2)으로 찾아가기 위해서는 |289 - 292|=3, 즉 -1을 3번해야 289 -> 17로 단 한 번의 행동으로 이동할 수 있어요. 그래서 따로따로 더해주는 게 맞습니다.

dannydino   4년 전

많은 도움 얻어갑니다! 일단 지금까지 도와주신정보로 고민해보고 풀어본 다음 그래도 안풀리면 또 여쭤보겠습니다.

감사합니다 :)

dannydino   4년 전

소스코드가 좀 더럽지만 결과값은 제대로 나오는 것 같습니다

시간초과로 자꾸 통과를 못하고 있는데 혹시 조금 더 최적화 하는 방법이 있을까요?

adh0463   4년 전

calculate 함수에서 iter를 통해 num 기준으로 iter^val을 찾으셨는데, 이러면 필요없는 구간까지 다 보게됩니다. 10^18을 넣어보니 2부터 한없이 다 보더군요..

방식만 거꾸로 해주시면 될 것 같아요

iter 고정해서 val을 찾는 방식이 아니라, val을 고정하고 iter를 찾는 방식으로 생각해보세요.

=====================================

하나의 예시를 들자면  num=10^18인 상태에서 val=11라면 iter의 후보군은 2,3,4,...,43,44로 줄일 수 있어요. 그런데 여기서 2, 3, ..., 42을 확인할 필요가 있을까요?

42, 43, 44만 확인해보면

42^11=717368321110468608

43^11=929293739471222707

44^11=1196683881290399744

보시면 num이 43^11과 44^11사이에 있는 걸 알 수 있습니다. 왼쪽은 43이 가장 가깝고, 오른쪽은 44가 가장 가깝습니다. 따라서 이 경우엔 43, 44만 보는 것이 최적입니다. 2부터 42까지 그리고 45부터 그 이후 수에 대해서는 가장 가까운 왼쪽 그리고 가장 오른쪽이 아니기 때문에 확인할 필요가 없어요.

======================================

위처럼 val을 고정하고 iter를 찾아가면 더 빠르게 후보군을 두 개 이하로 추릴 수 있어요.

좀 어려운 점은 여기서 왼쪽과 오른쪽을 계산할 때 이분탐색을 사용하셔야 합니다. 단순 iter++로는 시간초과가 날 것이 분명합니다. 저는 val을 고정한 상태에서 num보다 크고 오른쪽에서 가장 가까운 수를 구한다음 왼쪽을 (오른쪽-1)로 구해서 계산했어요.

마지막으로 같은 수를 여러번 방문하던데 그 부분도 신경써주셔야 합니다..

adh0463   4년 전

참고1) num=10^18일 때 특정 val에 대해 오른쪽(iter^val)을 표현할 수 없을 수 있습니다. c++ 기준으로 unsigned long long으로도 표현할 수 없는 수가 존재할 수 있어요.

참고2) 반례 

Input : 1134351241

Output : 9036

화이팅!

dannydino   4년 전

군대에있어서 바로 답변을 확인못했습니다 ㅠㅠ

먼저 친절하게 계속 답변해주셔서 정말 감사합니다!

답변해주신걸 보고 의문점이 든게

1. val을 고정시키고 iter을 찾는 방식으로 하더라도 val이 11일경우만 찾는것이아닌 val 이 2,3,4,... 그 이상의 수일 때도 찾아야하니 iter을 고정시키고 val을찾는방식과 똑같지 않나요?

2. 289처럼 (1->2->16->17->289)(2의 n제곱, 17의 n제곱) 두개 혹은 그 이상의 n제곱으로 이루어지는 수까지 찾으려면 logab 가 1보다 큰 모든 수에 대해서 탐색해줘야하는것아닌가요?

*반례가 나온이유가 확실한건아니지만 시간을 줄여본다고 currentMIN변수를 사용해서 거르는과정에서 오류가 생긴것같습니다..하핳;

dannydino   4년 전

currentMIN변수로 거르는과정을없에니 계산시간이 몇십배로늘어나는대신 결과는 제대로나오네요 ㅠㅠ

preview

adh0463   4년 전

군인이시군요. 무사히 전역하시길 바랍니다 ㅎㅎ;

1. 논리적으로 오류는 없더라도 탐색 범위가 다릅니다.

가령 N=24라고 생각해봅시다.

===============================================================

먼저 val을 고정시키고 왼쪽(L) 오른쪽(R)을 찾아봅시다

1) val=2 -> L=4, R=5

2) val=3 -> L=2, R=3

3) val=4 -> L=2, R=3

4) val=5 -> L=존재하지 않음, R=2

5) val=6 -> L=존재하지 않음, R=2

6) val=7 -> L=존재하지 않음, R=2

...

1-62) val=62 -> L=존재하지 않음, R=2

※ 모든 경우에 왼쪽 오른쪽 최대 2개밖에 나오지 않음.

===============================================================

반대로 iter를 고정시키고 찾아봅시다

1) iter=2 ->

1-1) iter^val <= N일 때 val의 최대값, val=4

1-2) iter^val >= N일 때 val의 최소값, val=5

2) iter=3 ->

2-1) iter^val <= N일 때 val의 최대값, val=2

2-2) iter^val >= N일 때 val의 최소값, val=3

3) iter=4 ->

3-1) iter^val <= N일 때 val의 최대값, val=2

3-2) iter^val >= N일 때 val의 최소값, val=3

...

언제까지?) log(num) / log(iter^val) === val이고, val <= 1이면 조건 종료..

num이 최대 10^18입니다. 위 조건에 따르면 val의 최소 정수값은 2입니다. num에 대해 sqaure root만큼 줄인다고 해도 iter가 최대 10^18까지 가버립니다.. 따라서 iter 고정하는 방식으로 가면 val을 예측할 수 없기 때문에 val을 고정하고 iter를 찾아가는 방식을 권유드린겁니당

2. 1.과 마찬가지로 val을 고정하고 현재 num에 대해 왼쪽과 오른쪽을 찾아주면 밑이 몇이든 상관이 없습니다..

가령 num=145에 대해 val=2라고 고정했을 때 왼쪽과 오른쪽의 밑이 될 iter는 각각 몇일까요 ?

12^2=144이니 왼쪽은 12이고 오른쪽은 13입니다. 이 처럼 val을 고정시켜버리면 바로바로 왼쪽과 오른쪽을 구할 수 있으십니다.

이 문제 어렵습니다. solved.ac 기준으로 플레티넘1로 난이도가 책정되어 있어요. 구현력과 가지치기, 정수론을 요구하는 문제입니다.

여기에 소스를 공개하기엔 다른 분들에게 스포가 될 수 있으니 adh0463@naver.com에 메일 주시면 제 소스라도 회신해드릴게요 ㅠ

adh0463   4년 전

아 중간에 오타가 났네요

num이 최대 10^18입니다. 위 조건에 따르면 val의 최소 정수값은 2입니다. num에 대해 sqaure root만큼 줄인다고 해도 iter가 최대 10^18까지 가버립니다.. 따라서 iter 고정하는 방식으로 가면 val을 예측할 수 없기 때문에 val을 고정하고 iter를 찾아가는 방식을 권유드린겁니당

-->

num이 최대 10^18입니다. 위 조건에 따르면 val의 최소 정수값은 2입니다. num에 대해 sqaure root만큼 줄인다고 해도 iter가 최대 10^9까지 가버립니다.. 따라서 iter 고정하는 방식으로 가면 val을 예측할 수 없기 때문에 val을 고정하고 iter를 찾아가는 방식을 권유드린겁니당

댓글을 작성하려면 로그인해야 합니다.