kkjhj77   2년 전

일단 제 소스의 예를 들면 x = 0 ,y = 11의 값을 입력을 받으면 이동거리는 1,2,3,2,2,1의 광년을 이동하여 최소 공간 이동장치작동 횟수(count)는 6이 됩니다.
이때  최대이동광년은  x + 지금까지 이동한 거리 + 1부터 최대이동거리의 총 합이 y 보다 커질때 까지 반복되면서 y보다 커질경우 이동거리를 -1 하거나 유지를 시켜서 x의값이 y의 값과 같을경우까지 반복을 하게 됩니다.
ex) x =0 y=11일 경우 처음에는 1의 이동거리를 가지게 되므로 Maxtravelrange = 1이 되며
travelrange=1, x=1 이된다. 그 다음은 Maxtravelrange은 1+2 가 되므로 총 3이 되며 travelrange=2가되며 x=3이된다.
그 다음은 Maxtravelrange은 1+2+3 =  6이 되며 travelrange=3, x=6이 되며
다음은 Maxtravelrange은 1+2+3+4=10이 되는데 x + Maxtravelrange = 16이므로 y값 보다 크므로
travelrange은 4가 되지않고 3값이 됩니다.
이때 stop 의변수 값은 1+2+3 = 6이 되는데 x의값이 6이므로 x + stop = 12가 되며 이는 y보다 값이 크기때문에 travelrange = 3-1 =2 가 되며 x +travelrange = 6+2 = 8이되며 이때 stop = 1+2 = 3이 됩니다.
그다음은 x+stop = 8 +3 =11 이므로 travelrange=2값으로 진행이 되며 x+travelrange = 8+2 = 10이 됩니다.
그 다음은 x+stop = 10+3 = 13 이므로 travelrange=2-1 =1이 되며 x+travelrange = 10 +1 = 11이 되며
x=y가 됬음으로 프로그램은 작동이 멈추게됩니다.
즉.  x=0  y= 11일 경우 
1. x=x+1            x=1               
2. x=x+2            x=3
3. x=x+3            x=6
4. x=x+2            x=8
5. x=x+2            x=10
6. x=x+1            x=11 =y   이므로 종료가 되며
총 6번의 횟수가 반복됩니다.
이게 프로그램 작동순서인데 답은 맞게 나오는데 자꾸 시간초과가 나와서 그러는데 어디가 잘못된걸까요??
말이 길고 어렵게 설명해서 죄송합니다.ㅠㅠㅠㅠ  많은 조언 부탁드립니다.

chogahui05   2년 전

오버플로우 같네요. 일정 범위 이상이 되면 터지는 걸로 봐서는..

kkjhj77   2년 전

댓글 감사드립니다.

죄송한데 혹시 어디서 오버플로우라는건지 알려주실수있나요 ??

seico75   2년 전

오답인가요? 시간 초과인가요?

일단 overflow 는 x+Maxtravelrange 에서 날 수 있을 것 같고, 

시간 초과는 22~24 에서 줄일 수 있을 거 같습니다.

* x, y 를 유지할 필요 없이 y-x 만 중요하므로 stop 을 for 돌리지 않을 수 있을 것 같습니다.

* sum(1~N) = (N+1)*N/2 를 이용하면 최대 N 광년까지 늘었다가 줄어들면 움직이는 거리는 N**2 이고 2N-1 번 움직인다는 것을 알 수 있을 것 같습니다. (1,2,3,4,.. N-1, N, N-1, .... 4, 3, 2, 1 ==> N + N - 1 = 2*N - 1)

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