[인프런] 연속된 자연수의 합

난이도

• Easy

문제 설명

N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요. 만약 N=15이면
7+8=15
4+5+6=15
1+2+3+4+5=15

입력 형식

• 양의 정수 N(7<=N<1000)

출력 형식

• 정수 : 총 경우의 수

예제 입력 및 출력

**예제 1:**
입력: n = 15
출력: 3

접근 방법

• 입력값 n 까지 순회하는 첫 번째 loop
• 두 번째 순회값은 첫 번째 순회 값에 1을 더한 값
• 임시값을 생성하고 순회할 값을 더한다
• 순회하고 더한 값이
  • n 보다 작으면 반복 순회
  • n 이랑 같으면 순회를 멈추고 경우의 수를 1 더한다
  • n 보다 커지면 순회를 멈추고 임시값을 0으로 되돌리고 순회를 멈춘다

    시간 및 공간 복잡도

• 시간 복잡도: O(n) - 두 번 순회 ( O(n * n))
• 공간 복잡도 : O(1) - 공간은 필요하지 않음

코드 구현

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int count = 0;
        for(int i = 1 ; i < n; i++){
            int temp = i;
            for(int j = i + 1; j < n; j++){
                temp += j;
                if(temp == n){
                    count++;
                    break;
                } else if(temp > n){
                    temp = 0;
                    break;
                }
            }
        }
        System.out.println(count);
    }
}