연속된 자연수의 합 2 (수학적풀이)

문제

풀이

import java.util.*;

class Main {
	public int solution(int n) {
			int answer = 0,cnt = 1;
			n -= cnt;
			while(n > 0) {
				cnt++;
				n = n - cnt;
				if(n%cnt == 0) answer++;
			}
			return answer;
		}
		    
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt(); 
		System.out.println(T.solution(n));
	}
	
}

풀이방법

그냥 와... 소리밖에 안나오는 풀이였다.
코드라고 생각하지 않고 본다면, 15라는 숫자를 만들기위해
연속된 n개 수를 구할려면, 1 + 2 + 3 + ... + n 값을 주고
15에서 (1+2+3...+n)를 뺀 후, 그 값이 n으로 딱 떨어져서 동등하게 분배를 해주면 된다.

예시)

연속된 두개의 수로 15가 만들어지려면 ㅁ + ㅁ공간에 1과 2를 할당해준다.
15-(1+2)을 2로 나누면 나머지는 0이고 몫은 6이다. 6을 1 과 2에 동등하게 분배시켜주면,
7+8이 되서 15가 만들어진다.

연속된 세개의 수로 15가 만들어지려면 ㅁ + ㅁ + ㅁ공간에 1과 2와 3를 할당해준다.
15-(1+2+3)을 3로 나누면 나머지는 0이고 몫은 3이다. 3을 1 과 2와 3에 동등하게 분배시켜주면,
4+5+6이 되서 15가 만들어진다.

연속된 네개의 수로 15가 만들어지려면 ㅁ + ㅁ + ㅁ + ㅁ 공간에 1,2,3,4를 할당해준다.
15-(1+2+3+4)를 4로 나누면 5/4로 나머지가 생긴다. 즉, 불가능하다.

연속된 다섯개의 수로 15가 만들어지려면 ㅁ + ㅁ + ㅁ + ㅁ + ㅁ 공간에 1,2,3,4,5를 할당해준다.
15-(1+2+3+4+5)를 5로 나누면 나머지는 0이고 몫은 0이다.
각각 0을 분배시켜주면 1+2+3+4+5가 되서 15가 만들어진다.

위 코드에서는, cnt가 자릿수를 나타내고 n이 타겟넘버(15)를 나타낸다.

맨 처음 n에서 cnt를 뺀것은 1+ 를 쓴것과 한것과 마찬가지다.
while문이 돌면, cnt는 1증가하고
n에서 cnt를 또 빼면 1+2를 쓴것이다.
n(=12) 가 cnt(=갯수)로 딱 떨어진다면 그 가능하다는 뜻이다.

while문이 계속 돌면서 cnt는 또 1 증가하고
n = 9가 된다. 그렇다면, 1+2+3 이 쓰여진것과 같은뜻이다.

이러한 과정을 거쳐 수학적으로도 연속된 수의 덧셈으로 나타낼 수 있는지 찾을수있다.