연속된 자연수로 더하여 자연수 n이 될 수 있는 가지수

• 내가 짠 코드 - 재귀 함수를 이용, 1 부터 시작해서 자연수 n 까지 연속된 수로 더해서 n이 나올 수 있는지 여부를 체크 함.

class Solution {
    
    public int solution(int n) {
        return countCase(1, n);
    }
    
    private int countCase(int start, int n) {

        if (start == n) {
            return 1;
        }

        int next = start * 2 + 1;
        if (next > n) {
            return countCase(++start, n);
        }

        int temp = n;

        for (int i = start; 0 < temp; i++) {
            temp -= i;
        }

        int isCase = temp < 0? 0 : 1;
        return countCase(++start, n) + isCase;
    }
}

 

• 수학 공식을 이용한 풀이 - 겁나 간단해 진다 -_-;

 for (int i = 1; i <= num; i += 2) {
        if (num % i == 0) {
            answer++;
        }
    }

저 문제를 수항 공식으로 만들어 보면..

 

1) n 이하의 숫자 a 부터 k 개의 숫자의 합이 n 이라는 가정의 수학 공식...

     a + (a+1) + (a+2) + ・・・・・・・・・・ + (a + k -1) = n

 

2) 1부터 100까지 더한 합은  101(=100 + 1) * 50(=100/2) 이라는 유명한 공식에 의거하여..

(a + (a + k - 1)) * (k / 2) = n

 

3) 한번더 다듬으면 이렇게 되고

 k(2a + k - 1) / 2 = n

 

4) a 만 남기고 나머지 항을 다 오른쪽으로 넘기면,

 a = n / k - (k - 1) /2

 

여기서 주목!!! 

a , n, k 모두 자연수가 되기 위한 조건

 

1. n/k 가 자연수가 되어야 함 -> k는 n 의 약수,  n > k

2. (k -1) / 2 가 자연수가 되어야 함으로 k 는 홀수

 

k = n보다 작으면서 n의 약수, 홀수 여야함....!!  그래서 결론..

 for (int i = 1; i <= num; i += 2) {
        if (num % i == 0) {
            answer++;
        }
    }