[백준/자바] 2018 수들의 합 5

[백준/자바] 2018 수들의 합 5

 

 

 

📌 문제 

어떠한 자연수 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을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

 

 

 

---

 

 

 

💎 문제분석하기

 

연속된 자연수를 포착해야 하므로 투 포인터를 사용하면 쉽게 풀 수 있다. 

 

투 포인터는 시작과 종료 지점을 나타내주는 포인터로, 시작 인데스, 종료 인덱스를 지정한다. 

 

 

먼저 풀이에서 사용할 변수를 정한다. 

 

N을 받았고 답을 찾기 위한 sum, sum이 발생하는 횟수를 세는 count

 

N

sum

count 

startIdx

endIdx

 

N 스스로를 세는 1이 항상 존재하므로 sum =1, count =1로 시작한다. 

 

카운터를 이동해가면서 count를 세면 된다. 이때 규칙은 

 

 

 

 

1 ) sum이 N이 맞으면 Count +1 와 end를 뒤로 이동  

2) sum이 N보다 크면 start를 뒤로 이동 

3) sum이 N보다 작으면 end를 뒤로 이동 

 

 

 

 

💡 코드 구현하기

 

import java.util.Scanner;

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

		int N = sc.nextInt();
		int count = 1;
		int startIdx = 1;
		int endIdx = 1;
		int sum = 1;

		while (endIdx != N) {
			if (sum == N) {
				count++;
				endIdx++;
				sum = sum + endIdx;
			} else if (sum > N) {
				sum = sum - startIdx;
				startIdx++;
			} else {
				endIdx++;
				sum = sum + endIdx;
			}
		}

		System.out.println(count);
	}
}

 

 

 

 

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편