숫자의 표현

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12924

❔ 문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다.

예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성하세요.

⚠️ 제한사항

• n은 10,000 이하의 자연수 입니다.

---

💡 풀이 (사용언어 : Java & Python)

Java

class Solution {
    public int solution(int n) {
        // 자기 자신의 경우의 수 +1
        int count = 1;
        // 연속된 수이기 때문에 그 수의 절반 언저리부터 체크하면 된다
        for (int i = n/2 + 1; i > 0; i--) {
            int sum = 0;
            // 1씩 감소하면서 합해주고 총합이 정답이거나 정답보다 커지면 탈출
            for (int j = i; j > 0; j--) {
                sum += j;
                if (sum == n) {
                    count++;
                    break;
                }
                if (sum > n)
                    break;
            }
        }
        return count;
    }
}

Python

def solution(n):
    # 자기 자신 경우의 수 미리 포함
    answer = 1
    # 절반 언저리 부터 시작
    k = n // 2 + 1
    flag = True
    
    while(flag):
        ssum = 0
        kk = k
        # 연속된 수의 합이 n보다 크면 중단하고 1작은수로 다시 누적합 시작
        while(ssum <= n):
            ssum += kk
            # 정답 발견하면 그만 계산하고 다음 케이스로 이동
            if ssum == n:
                answer += 1
                break
            # 끝에 1까지 찍으면 더이상 경우의 수 존재 안하므로 전체 종료
            if kk == 1:
                flag = False
                break
            kk -= 1
        k -= 1
    
    return answer

• 참고할 만한 풀이 (n의 약수 중 홀수의 개수가 답)

15를 예로 생각해보면
15의 홀수인 약수는 1,3,5,15가 있습니다.

1) 약수가 1
1로 인해 15는 연속하는 하나의 자연수, 15로 이루어져 있음

2) 약수가 3
3으로 인해 15는 5+5+5 의 합으로 표현, 조작을 통해 4+5+6 

3) 약수가 5
5도 마찬가지로 3+3+3+3+3 즉, 1+2+3+4+5 로 표현이 가능

4) 약수가 15
15 경우는 위의 1) 2) 3) 과는 조금 예외적이다.  
모든 홀수 2n+1는 n 과 n+1, 연속하는 두 수의 합으로 표현 할 수 있으므로 
이 경우에는 7+8

def expressions(n):
 
    return len([i  for i in range(1, n+1, 2) if num % i is 0])