[브론즈 1] 백준 1834번 자바(JAVA) - 나머지와 몫이 같은 수

문제

N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

입력

첫째 줄에 2,000,000 이하의 자연수 N이 주어진다.

출력

첫 줄에 구하고자 하는 수를 출력한다.

---

첫번째 시도

1. 먼저 시간제한을 봤다.

2. while문으로 하나씩 증가시키면서 값을 찾는 무식한 방법이 가능할까?

3. 시간 제한상 불가능할 거라 생각했다.

 

두번째 시도

1. 규칙을 찾아보자 

 

N = 1 -> x

N = 2 -> 3

N = 3 -> 4, 8

N = 4 -> 5, 10, 15

 

2. 나머지와 몫이 모두 같은 자연수의 갯수는 N-1개가 나온다.

3. 나머지와 몫이 모두 같은 자연수를 찾는다는 방법보다

나머지와 몫이 모두 같은 자연수를 만들어 가는 방법이 효율적이라고 생각했다.

 

즉

i <= N-1

(N * i(몫))  + i(나머지) = 나머지와 몫이 모두 같은 자연수로 등장한다.