섹션 3. Two pointers, Sliding window[효율성 : O(n^2)-->O(n)] 5. 연속된 자연수의 합

문제

• 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. N을 입력받는다. 이번 문제는 메소드에서 배열을 선언해야 한다.

 

2. 메소드 구현으로 넘어가보자.

 

3. result, sum, lt를 선언하고 0으로 초기화한다.

• result : 결과값
• sum : N과 비교하기 위한 누적 합산값
• lt : 포인터로, 왼쪽부터 시작한다.

4. M을 선언하는데, 입력받은 N을 2로 나누고 1을 더한 값을 넣어준다.

• 2개 이상의 연속된 자연수의 합을 구하는 것이고, N만큼 for문을 돌리지 않고 M만큼만 돌려도 충분하다.
• M = (N / 2) + 1

5. M의 크기를 가진 배열 arr[ ] 을 선언한다.

 

6. 0부터 M까지 도는 for문을 선언하고, arr 배열에 i + 1 값을 넣는다.

• i는 인덱스 값으로 0~14까지 생성되는데, 우리에게 필요한 값은 1~15이므로 1씩 더해서 배열에 넣어준다.

7. 또 다른 0부터 M까지 도는 for문을 작성하고 rt를 선언해서 범위를 설정한다. 

• rt : 포인터로, 오른쪽부터 시작한다.
• M 크기를 가진 윈도우라고 생각하자.

8. 맨 처음에는 arr[rt] 값을 sum에 누적한다.

• sum에는 arr[lt] 부터 arr[rt]까지의 합이 들어간다.

9.  sum과 M이 동일한지 비교하고, 동일하면 결과값에 1을 더한다.

 

10. sum이 M보다 크거나 작을때까지 도는 while 문을 작성한다.

 

11. sum에서 arr[lt] 값을 뺀 후에 lt를 더해준다.

• 맨 처음과 마지막 인덱스를 통해 sum 값을 변경하는 것이다.
• 아래 이미지를 참고하여 이해해보자.
• sum 값이 15가 넘지 않을 때까지 rt만 계속 증가하고, 아래처럼 1+2+3+4+5가 되었을 때 비로소 15가 되어서 result가 1 증가한다.

• rt가 또다시 1 증가하면 sum이 15가 넘으므로 lt가 1 증가하고, arr[lt] 값이 빠진다. 이 과정을 sum이 15가 되는 범위가 새로 나올때까지 반복한다.

수행 결과를 확인한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.