2014년 7월 17일 목요일

1834 - 나머지와 몫이 같은 수

N = 1 일 때
N = 2 일 때
N = 3 일 때

자연수 1 부터 적당한 수까지 직접 해보면 규칙이 보인다.

규칙을 찾기 힘들다면 아래를 참고해보자.
  •  나머지(R)는 나누는 수(N)보다 클 수 없다.

그럼 이렇게 생각해 볼 수 있다.
  • N으로 나누었을 때 나올 수 있는 나머지의 종류는 0, ... N-1 이다.

이 말을 다시 해석하면
  • R = [0, ... N-1] 인 수열에 대해, Ak = k * Rk + Rk (k ≥ 0) 인 수열의 합이다.
    (Rk은 몫이지만 나머지와 같고, Ak 는 원래의 숫자를 도출한 것이다.)
수열 A에 있는 원소들의 합이 곧 정답이다. 수열 A부터 살펴보면,
Ak = k * Rk + Rk = k * (Rk + 1) 로 나타낼 수 있고
이 수열은 A0 = 0, A1 = 1 * 2, A2 = 2 * 3 ... 이런식이다.

점화식으로 풀어내자면,
A0 + A1 + ... + An-1> + An = ( 0 * 1 ) + ( 1 * 2 ) + ... ( (n-1) * n ) + ( n * (n+1) )
  = (n-1) * n * (n+1) / 2     ∵ 합 공식
  = (n2 - 1) * n / 2        ∵ 합차공식


PS. 나머지와 몫을 묶어서 설명했는데, 몫이 0 일 경우는 없을 것이므로, A0 은 무시해도 된다.
PS. 몫은 quotient, 나머지는 remainder.
댓글 쓰기

게시글 목록