[Silver V] 수들의 합5_P2018

[성능 요약]

메모리: 17676 KB, 시간: 256 ms

[분류]

수학(math), 두 포인터(two_pointer)

[문제 설명]

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

[입력]

첫 줄에 정수 N이 주어진다.

[출력]

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오.

 

 

---

 

 

import java.util.Scanner;
public class P2018_연속된자연수의합 {
    public static void main(String[] args){
        // 투포인터 사용하기
        // 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현한다.
        // 연속된 수의 합 담는 변수 : sum
        // 연속된 자연수의 합 나타내는 가짓수 담는 변수 : count
        // 연속된 수의 합의 범위를 지정할 두개의 포인터 변수 : start, end
        // 연속된 수의 합 범위의 시작점 : start
        // 연속된 수의 합 범위의 끝점 : end

        // 1. start, end 는 먼저 숫자 1에서부터 시작한다.
        // 2. end 가 end++ 되면서 sum 변수에 더해진다.
        // 3. 이때 sum 값이 N 값 보다 작으면 end ++ 증가하고 합 변수에 더해서
        //    sum = sum + end; 로 변경된다.
        //    (주어진 수보다 합이 작다는것은 합이 더 커져야한다는것!
        //     따라서 연속된 자연수의 범위를 넓혀 합을 증가해줘야하므로
        //     end 계속 ++ 시키면서 sum == N 이 될때까지 반복한다.)
        // 4. 또는 sum 값이 N 값 보다 크면 sum = sum - start 로 변경되고 start ++ 증가한다.
        //    (sum 값이 N 보다 크면 그 연속된 자연수의 범위는 더이상 볼 필요가 없어진다.)
        //    (따라서 start 를 ++ 증가시킴으로 새로운 범위의 시작점을 변경시켜
        //     새로운 범위를 만든다.)
        // 5. 아니면 sum 값이 N 값과 같다면 count++ 해주고 end++ 해준다.
        // 6. 이렇게 end 가 N-1 까지 도달하게 될때까지 반복한다.
        //    N 까지 가지 않는 이유는 N을 연속된 자연수의 합으로 표현하는 방법 중 하나가
        //    N 자기자신이기 때문이다. 모든 자연수는 일단 본인 자기자신만으로
        //    연속된 합을 표현할 수 있어서 가짓수 count는 1부터 시작하게 되는 것이다.


        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        // 입력받은 값 N
        int sum = 1;
        // 현재 연속된 합 담는 변수 sum
        // (숫자 1부터 시작하므로 1로 초기화 해줘야함. 0으로 초기화하면 틀림..)
        int count = 1;
        // 가짓수 담는 변수 count
        // (1부터 시작하는 이유
        //  : 예를 들어 15가 연속된 자연수들의 합을 나타내는 방법에는 15, 7+8, .. 이렇게 있다.
        //  여기서 자기 자신으로 나타내는 방법(15)도 포함이기 때문에
        //  가짓수가 무조건 한가지는 있는 것이다.)
        int start = 1;
        // 연속된 자연수의 합의 범위 시작점이 되는 변수 start
        int end = 1;
        // 연속된 자연수의 합의 범위 끝점이 되는 변수 end

        while(end != N) { // end_index 가 배열 끝 인덱스 되기 전까지 반복한다.
            // 1) sum == N 인 경우
            if(sum == N) {
                count++;
                end++;
                sum += end;
            }
            // 2) sum > N 인 경우
            else if(sum > N) {
                sum -= start;
                start++;
            }
            // 3) sum < N 인 경우
            else {
                end++;
                sum += end;
            }
        }

        System.out.print(count);
    }
}

 

 

 

[ 슈도코드 작성 ]

N 변수에 입력받은 값 저장

사용 변수 초기화 ( sum = 1, count = 1, start = 1, end = 1 )

while ( end != N ) {

    if ( sum == N ) // sum과 N 값이 같은 경우

        count 증가, end 증가, sum = sum + end 값으로 변경

    else if ( sum > N ) // sum이 N 보다 큰 경우

        sum = sum - start 값으로 변경, start 증가

    else                    // sum이 N 보다 작은 경우

        end 증가, sum = sum + end 값으로 변경

}

 

count 출력하기

 

 

 

 

---

 

 

// ex) N = 10

// start = 1, end = 1, sum = 1, count = 0 으로 시작한다.

    1      2     3     4     5     6     7     8     9     10
 start
 end

 

// 이때 sum(= 1) < N(= 10) 이므로 end++(2)가 되고 sum += end 로 sum = 1 + 2 = 3 이 된다.

   -> start = 1, end = 2, sum = 3, count = 1

    1      2     3     4     5     6     7     8     9     10
 start
         end

 

// 아직도 sum(=3) < N(=10) 이므로 end++(3)이 되고 sum += end 로 sum = 3+3 = 6 이 된다.

   -> start = 1, end = 3, sum = 6, count = 1

    1      2     3     4     5     6     7     8     9     10
 start
                 end

 

// 여전히 sum(=6) < N(=10) 이므로 end++(4)가 되고 sum += end 로 sum = 6 + 4 가 된다.

   -> start = 1, end = 4, sum = 10, count = 1

    1      2     3     4     5     6     7     8     9     10
 start
                       end

 

// 이번에는 sum(=10) = = N(=10) 이 되어서 count++(2) 해준다.

  그리고 연속된 수의 합 범위를 새롭게 변경시키게 하기 위해 end++(5)로 해줌으로써

  다음 순서에서 sum > N이 되게하여 범위를 변경시키게 만든다.

  그리고 sum 값을 다음과 같이 변경해줘야 한다. => sum = sum + end = 10 + 5 = 15

   -> start = 1, end = 5, sum = 15, count = 2

    1      2     3     4     5     6     7     8     9     10
 start
                              end

 

// 이번 순서에서는 sum(=15) > N(=10) 가 되었다.

   여기서 end++ 해서 sum += end 해봤자 sum 값은 주어진 N=10 보다 더 커지므로

   더이상 이 연속된 수의 범위에서는 어떻게든 end++ 해서 sum 에 더해줘도 우리가 원하는 수

   10이 되지 못한다. 따라서 새로운 연속된 자연수의 범위로 변경시켜줘야한다.

   HOW? 어떻게?? 연속된 자연수들의 범위의 시작점인 start 변수를 ++ 해줌으로서 범위를 변경해준다.

   start++ 하기 전에 먼저 sum 값에서 start 값을 빼줘야한다.

   왜냐하면 현재의 start 값은 이제 연속된 자연수의 합 범위에서 제외되기 때문에

   합 sum 변수에서 빼줘야한다. sum = sum - start = 15 - 1 = 14 가 되고 그 후에 start++(2) 를 해준다.

   -> start = 2, end = 5, sum = 14, count = 2

    1      2     3     4     5     6     7     8     9     10
         start
                              end

 

// 이번 순서에서도 sum(=14) > N(=10) 이 되었다.

   여기서도 마찬가지로 sum = sum - start = 14 - 2 = 12 로 값을 변경해주고

   start++(3)을 해주면서 연속된 자연수의 합 범위를 새롭게 변경해준다.

   -> start = 3, end = 5, sum = 12, count = 2

    1      2     3     4     5     6     7     8     9     10
                start
                              end

 

// 이번 순서에서도 sum(=12) > N(=10) 이므로 sum = sum - start = 12 - 3 = 9 로

   변경해주고 start++(4)로 범위를 변경해준다.

   -> start = 4, end = 5, sum = 9, count = 2

    1      2     3     4     5     6     7     8     9     10
                      start
                              end

 

// 이번 순서에서는 sum(=9) < N(=10) 이므로 end++(6)으로 범위를 더 넓히고

   sum = sum + end = 9 + 6 = 15로 연속된 합의 값을 변경해준다.

   -> start = 4, end = 6, sum = 15, count = 2

    1      2     3     4     5     6     7     8     9     10
                       start
                                     end

 

// 이번 순서는 sum(=15) > N(=10) 이므로 다음과 같이 된다.

   -> start = 5, end = 6, sum = 11, count = 2

    1      2     3     4     5     6     7     8     9     10
                             start
                                     end

 

// 이번 순서에서도 sum(=11) > N(=10) 이므로 다음과 같이 된다.

   -> start = 6, end = 6, sum = 6, count = 2

    1      2     3     4     5     6     7     8     9     10
                                     start
                                     end

 

// 이번 순서에서는 sum(=6) < N(=10) 이므로 end++(7)을 해주고

   sum = sum + end = 6 + 7 = 13으로 값을 변경해준다.

   -> start = 6, end = 7, sum = 13, count = 2

    1      2     3     4     5     6     7     8     9     10
                                     start
                                             end

 

// 이번 순서에서는 sum(=13) > N(=10) 이므로 연속된 자연수 합 범위를 새롭게 바꿔야 하므로

   다음과 같이 된다.  => sum = sum - start = 13 - 6 = 7, start++(7)

   -> start = 7, end = 7, sum = 7, count = 2

    1      2     3     4     5     6     7     8     9     10
                                           start
                                            end

 

// 이번 순서에서는 sum(=7) < N(=10) 이므로 합을 더 증가시켜줘야하므로 다음과 같이 된다.

   end++(8), sum = sum + end = 7 + 8 = 15

   -> start = 7, end = 8, sum = 15, count = 2

    1      2     3     4     5     6     7     8     9     10
                                           start
                                                   end

 

// 이번 순서에서는 sum(=15) > N(=10) 로 범위를 새롭게 변경해야 하므로 다음과 같이 해준다.

   sum = sum - start = 15 - 7 = 8, start++(8)

   -> start = 8, end = 8, sum = 8, count = 2

    1      2     3     4     5     6     7     8     9     10
                                                  start
                                                   end

 

// 이번 순서는 sum(=8) < N(=10) 으로 다음과 같이 되야 한다.

   -> start = 8, end = 9, sum = 17, count = 2

    1      2     3     4     5     6     7     8     9     10
                                                  start
                                                          end

 

// 이때 end == N - 1 = 9 에 도달했으므로 더이상 반복해서 확인하지 않게 된다.

   이제 count = 2 를 출력하면 우리가 원하는 주어진 숫자 N = 10을

   연속된 자연수들의 합으로 나타낼 수 있는 가지수는 2가지(10, 1+2+3+4)이다.