[인프런 알고리즘] Chpater 3, 5번 문제(연속된 자연수의 합)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

첫 번째 코드(투 포인터 + 슬라이딩 윈도우)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class sec03_05 {
    public static int solution(int N) {
        int count = 0, sum = 0;
        int lPtr = 0, halfPlusOne = (N / 2) + 1;
        int[] arr = new int[halfPlusOne];

        for(int i = 0; i < halfPlusOne; ++i) arr[i] = i + 1;

        for(int rPtr = 0; rPtr < halfPlusOne; ++rPtr)
        {
            sum += arr[rPtr];
            while (sum > N) sum -= arr[lPtr++];
            if(sum == N) ++count;
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(solution(N));
    }
}

 

두 번째 코드(수학적 접근)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class sec03_05 {
    public static int solution(int N) {
        int count = 0, temp = 1;
        --N;
        while (N > 0)
        {
            N = N - (++temp);
            if(N % temp == 0) ++count;
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(solution(N));
    }
}

 

설명

첫 번째 코드 설명

• 투 포인터와 슬라이딩 윈도우 알고리즘을 사용한다.
• (N / 2) + 1 까지의 배열을 생성한다.
• 두 개의 포인터(lPtr, rPtr)와 합(sum)을 사용하여 연속된 수의 합을 구한다.
• sum이  N 보다 크면 lPtr을 오른쪽으로 이동시켜 sum을 줄인다.
• sum이  N 과 같아지면 경우의 수를 증가시킨다.

(N / 2) + 1 까지의 배열을 생성하는 이유는, 연속된 자연수의 합으로 숫자 N 을 표현할 때, 최소 두 개의 숫자의 합이 N 이 되어야 하기 때문이다. 이를 통해 불필요한 계산을 줄이고, 효율적으로 답을 찾을 수 있다.
1.어떤 자연수 N 을 연속된 자연수의 합으로 나타낼 때, 최소 두 개 이상의 수가 필요하다.
예를 들어, N = 15 인 경우, 최소 두 개의 연속된 수가 합쳐져서 15가 되어야 한다.

2.만약 N 이 15라면, 15 를 넘지 않으면서 연속된 수의 합으로 나타낼 수 있는 가장 큰 자연수는 15의 절반인 7.5이다. 실제로 N/2 를 넘는 숫자부터는 N 을 넘지 않으면서 연속된 자연수의 합으로 표현할 수 없다.
예를 들어, N = 15 일 때 8 이상의 수를 시작점으로 연속된 합을 만들 수 없다.

3.N/2 까지만 배열을 생성하면, 불필요한 연산을 줄일 수 있다. 예를 들어, N = 15 인 경우 N/2 = 7.5 이고, 여기에 1을 더해 8까지의 배열을 생성하면 충분하다.
따라서 halfPlusOne = (N / 2) + 1은 최적화된 범위이다.

 

두 번째 코드 설명

• 초기설정
  -count는 연속된 자연수의 합으로  N 을 나타낼 수 있는 방법의 수를 세는 변수이다.
  -temp는 현재 연속된 자연수의 개수를 나타내는 변수로, 초기값은 1이다.
  -N 에서 1을 뺀 값으로 시작한다.
• 루프
  -N 이 0보다 클 때까지 반복한다.
  -N 에서 temp를 증가시킨 값을 뺀다.
  -현재  N  값이 temp로 나누어 떨어지면, 연속된 자연수의 합으로  N 을 나타낼 수 있는 경우이므로 count를 증가시킨다.
• 예를 들어,  N = 15 일 때:
  -초기값:  N = 14 , temp = 1
  -첫 번째 루프:  N = 14 - 2 = 12 , temp = 2, 12 % 2 == 0 -> count = 1
  -두 번째 루프:  N = 12 - 3 = 9 , temp = 3, 9 % 3 == 0 -> count = 2
  -세 번째 루프:  N = 9 - 4 = 5 , temp = 4, 5 % 4 != 0
  -네 번째 루프:  N = 5 - 5 = 0 , temp = 5, 0 % 5 == 0 -> count = 3