zakelstorm   5년 전

제가 생각한것은

N번째 징검다리를 밟기 위해 최대한 많은 징검다리를 밟는다는것은

1+2+3+...+s + α = N (1~s는 1씩증가하는 연속된 숫자, α는 s보다 큰 수)

ex) 9(N) = 1+2(s)+6(α)

56(N) = 1+2+3+...+9(s)+11(α)


이면 된다고 생각해서 공식을 이용해서 이렇게 코드를 짰습니다.

어떤 점에서 잘못된 생각을 가졌던 걸까요?


namnamseo   5년 전

식을 검토해보지는 않았지만 아마 sqrt가 실수 연산이라서 생긴 오류같아요.

round()를 해보세요.

zakelstorm   5년 전

오 감사합니다. 단번에 됐습니다.

실수는 정수로 바꿔줘야 올바른 결과가 나오는군요

namnamseo   5년 전

다행이네요! 그래서 sqrt는 정수만 써서 이분 탐색으로 구하기도 해요.

cbj2741   1년 전

안녕하세요 혹시 저도 이분탐색이 아니라 작성자님처럼 똑같이 접근을 해서 풀고 있었습니다.

그런데 저는 도저히 x = (-1+sqrt(1+8*N))/2; 이 식을 도출해내지 못했습니다.

1~2 ->1

3(1+2) ~ 5 ->2

6(1+2+3)~9 -> 3 이런식으로 쭉 써내려봤는데도 도출을 못했습니다 비록 4년전 글이지만 혹시 식이 어떻게 도출된건지 설명을 해주실수있나요?

제가 작성자님의 식을 보고 최대한 접근해보려했지만 실패했습니다

우선 s의 값만 알수 있다면 정답은  s+1이기에

N=s(s-1)/2+α 

식에서

s^2-s+2(α-N)=0에서 근의 공식으로 풀어보려했습니다.

계산해보니 일단 α의 범위가  s+1<=α<=2s  (s>1) 이더라구요...

그런데 도저히 작성자분의  

x = (-1+sqrt(1+8*N))/2; 식에는 도달하지 못하였습니다...

혹시 답글 남겨주실 수 있다면 감사합니다

namnamseo   1년 전

원 글의 작성자는 아니지만 답변 드려봅니다.

우선, 이런 생각이 있습니다.
s번 점프해서 10번 칸에 도달할 수 있다고 칩시다.
그러면 그때의 방법을 이용해서, s번 점프해서 11번 칸에 도달할 수 있을까요?

네, 가능합니다. 마지막 점프를 한 칸 더 길게 가져가면 되겠죠. (이러면 규칙을 위반하지 않습니다.)
그럼 그게 가능하다면 마찬가지로 12번, 13번, …….
즉, 10번째 이후의 모든 칸에 정확히 s번 점프해 도달할 수 있겠습니다.

그렇다면, s번 점프해서 도달할 수 있는 칸의 번호들을 모아놓고 보면,
[10, 13, 15, …] 이렇게 빈 칸이 있을 순 없고,
[10, 11, 12, 13, …] 이렇게 어떤 숫자 이후의 모든 숫자가 모이게 될 겁니다.

즉, s번 점프해서 도달할 수 있는 칸의 번호에는 어떤 최소값이 있으며
그 최소값 이상의 모든 번호에 도달할 수 있을 겁니다.

또, 그 최소값은 당연히 (1+2+…+s)=(s+1)×s/2이겠습니다.

그럼, s번 점프해서 정확히 N번째 칸에 도달하려면, 이런 식을 세울 수 있습니다.

(s+1)×s/2 ≤ N.

이제, 이 식을 만족하는 가장 큰 정수 s를 찾아야 합니다.

예를 들어, N=8이라고 합시다.
s=3일 때 좌변은 6 < N이고,
s≒3.5311일 때 좌변이 정확히 8 = N이 되고,
s=4일 때 좌변은 10 > N입니다.

저 중간에 N이 되는 지점에서의 s를 구할 수 있다면,
문제의 정답(좌변 ≤ N인 가장 큰 s)을 어떻게 구할 지 아시겠나요?

여기서는 3.5311의 소수점 부분을 버린 3이 답이 되겠죠.

즉, (s+1)×s/2 = N 이 되는 s를 찾아 소수점 부분을 버려야 하겠습니다.
그 s를 찾는 공식이 근의 공식에 의해 (1/2)·(sqrt(8N+1)-1) 이구요.
C/C++에서는 정수형에 실수를 담으면 자동으로 소수점 아래가 버려지기 때문에 위와 같은 소스 코드를 짤 수가 있습니다.


4년이 지나서 다시 보니, 원래 소스의 어떤 점이 틀렸는지는 잘 모르겠습니다.
지금 다시 저 소스를 제출해 보니 맞았다고 나오네요.

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