[백준]2018_투포인터

인프런 코딩테스트 강의를 들으며 백준 2018번 문제를 풀어보았다.

 

링크

 

https://www.acmicpc.net/problem/2018

 

 

 

문제

어떠한 자연수 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을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

풀이

투 포인터. 그러니까 start_index와 end_index를 가지고 푸는 문제이다. 딱히 배열을 사용할 필요도, for문을 사용할 필요도 없어 시간 복잡도가 2N이면 끝난다.

 

코드

import java.util.Scanner;

public class Back_2018투포인터 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int count = 1, start_index=1, end_index=1,
				sum=1;
		while(end_index != N) {
			if(sum == N) {
				count++;
				end_index++;
				sum += end_index;
			}
			else if(sum>N) {
				sum -= start_index;
				start_index++;
			}
			else if(sum<N) {
				end_index++;
				sum+= end_index;				
			}
		}
		System.out.println(count);

	}

}

 

처음에 배열 하나를 무의식 적으로 만들었다. 풀이 그림에서 배열과 같은 그림이 있었기 때문이다. 그런데 이건 그럴 필요가 없는 문제였다. 반복문은 항상 for문으로 써서 무조건적으로 for문으로 어떻게 해결하나 생각했었는데 while문으로도 쉽게 해결이 되는 문제였다. 코드의 가독성도 높다고 생각한다.