[Two pointers] 연속된 자연수의 합

 

 

 

설명

N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.

만약 N=15이면

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

와 같이 총 3가지의 경우가 존재한다.

 

 

 

 

입력

첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어집니다.

 

 

 

 

출력

첫 줄에 총 경우수를 출력합니다.

 

 

 

 

예시 입력1

15

 

 

 

예시 출력1

3

 

 

 

 

 

풀이

n이 주어지면, n/2의 몫 + 1 까지의 자연수만 있으면 된다.

• 15를 예로 들면, 가장 큰 연속된 자연수는 15/2의 몫인 7과 하나 더 큰 수인 8이다.
  즉, 8까지의만 자연수만 있으면 되는 것이다.
  
  

 

1부터 n/2의 몫 + 1 까지의 값을 배열에 넣는다.
초기값이 0이고 배열의 인덱스를 가리키는 lt와 rt가 있다.

 

rt를 0부터 배열 크기만큼 돈다.

• 배열의 rt 값을 sum에 더한다.
• sum이 n과 같다면 정답 카운팅 변수를 1 증가시킨다.
• sum이 n보다 클 때 까지 다음 로직을 돈다.
  • 현재 배열의 lt 값을 sum에서 빼고, lt 값을 1 증가시킨다.
  • sum이 n과 같다면 정답 카운팅 변수를 1 증가시킨다.

 

 

 

 

코드

package inflearn._9_5;

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

public class Main {

    public static int solution(int n ) {

        int answer = 0, sum = 0, lt = 0;
        int m = n/2 + 1; // 연속된 자연수가 몇까지 필요한지, ex) 15/2 + 1 = 8

        int [] arr = new int[m];

        // 초기값 설정
        for(int i = 0; i < m; i++) {
            arr[i] = i+1;
        }

        for(int rt = 0; rt < m; rt++) {
            sum += arr[rt];
            if (sum == n) {
                answer++;
            }
            while (sum >= n) {
                sum -= arr[lt++];
                if (sum == n) {
                    answer++;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        bw.write(sb.append(solution(n)).toString());
        bw.flush();

        bw.close();
        br.close();

    }
}