백준 2018번 자바

문제

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

2018번: 수들의 합 5

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int cnt = 0;
		int sum = 0;
		int m = 1;
		
        if (N == 1) {
			System.out.println(1);
			return;
		}
        
		for (int i=m; i<=N; i++) {
			sum += i;
			if (sum > N) {
				m++;
				i = m;
				sum = i;
				continue;
			}
			
			if (sum == N) {
				cnt++;
				m++;
				i = m;
				sum = i;
			}
			
		}
		System.out.println(cnt+1);
	}
}

1. 처음에 2중 for문으로 문제 해결을 시도했으나 시간초과로 for문을 한번 돌려서 해결하는 방법을 모색했다.

 

2. 특정 상황(sum > N or sum == N)이 생겼을 때 변수m의 값을 변화시켜 해당 지점부터 다시 탐색하도록 유도해 답을 이끌어 냈다. 마지막 출력때 cnt+1은 N을 만드는 연속된 자연수의 경우의 수 중에서 N자신을 포함 시킨것이다. sum > N때문에 N/2부터는 탐색을 할 수 없기때문이다.

 

3. 어찌저찌 정답을 맞췄지만 이보다 조금 더 시간을 단축할 수 있는 방법은 '투포인터' 라는 개념의 활용이다.

start_index	end_index
1	2	3	4	5	6	7

개념 자체는 간단하다. 예를들어 for문을 돌릴 경우 변수 i의 값으로 포인터를 활용해 답을 탐색한다면 투포인터는 start_index와 end_index 두 개의 포인터로 답을 탐색하는 것이다. 이 방법으로 할 경우 위 답과 약 80ms 정도 차이가 나게 된다. 아래는 투포인터를 활용한 해답이다.

import java.util.Scanner;
public class P2018_연속된자연수의합 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int count = 1;
    int start_index = 1;
    int end_index = 1;
    int sum = 1;
    while (end_index != N) {
      if (sum == N) {         //sum == N ->  End index++;  sum = sum + End index;  count++;  
        count++;
        end_index++;
        sum = sum + end_index;
      } else if (sum > N) {   //sum > N ->  sum = sum - Start index;  Start index++;
        sum = sum - start_index;
        start_index++;
      } else {                //sum < N ->  End index++;  sum = sum + End index;
        end_index++;
        sum = sum + end_index;
      }
    }
    System.out.println(count);
  }
}
// 출처 https://github.com/doitcodingtestjava/answer/blob/main/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/P2018_%EC%97%B0%EC%86%8D%EB%90%9C%EC%9E%90%EC%97%B0%EC%88%98%EC%9D%98%ED%95%A9.java

 

정리 : 문제 난이도가 어렵지 않아 투포인터를 몰라도 해결 할 수 있었지만 비슷한 류의 문제를 풀 때 좋은 방법이니 확실하게 배워두자