3-6. [투 포인터]연속된 자연수의 합 구하기

수들의 합 5 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

32 MB

7943

3611

2789

49.059%

문제

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

예제 입력 1 복사

15

예제 출력 1 복사

4

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO March 2003 Contest > Orange 2번

• 데이터를 추가한 사람: momiens
• 문제의 오타를 찾은 사람: yukariko

---

풀이

1. 로직구성
   1. sum > N => start_index++
   2. sum < N => end_index++
   3. sum === N => count++
2. 변수
   1. count = 1
      1. 1인 이유는 가장 마지막 것을 고르면 항상 N이기 때문이다.

 

코드

const N = 15;
let count = 1;
let sum = 1;
let start_index = 1;
let end_index = 1;

for (let i = 0; i < N; i++) {
  if (sum === N) {
    end_index++;
    sum += end_index;
    count++;
  } else if (sum < N) {
    end_index++;
    sum += end_index;
  } else {
    sum -= start_index;
    start_index++;
  }
}

console.log(count);