[백준 2018] 수들의 합5 (JAVA)

🔰 문제

💡 접근방식

처음엔 N의 크기를 유심히 안 보고, 떠오르는 대로 풀어서 완전 탐색 방식으로 풀었다.
TLE가 안 나고 통과하긴 했지만, 정석적으론 투포인터로 푸는 문제이다.

📌 투포인터란?

투포인터 알고리즘은 슬라이딩 윈도우라고 불리기도 한다.
N의 값이 매우 커서 완전 탐색 방식으로 풀면 시간초과가 날 때 투포인터를 풀면 해결할 수 있다.

1차원 배열이 있고, 배열 안에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 설정한다.
2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘.

예를 들어 N칸짜리 1차원 배열이 있을 때, 부분배열의 원소 합이 M이 되는 경우의 수를 구한다. 완전 탐색으로 풀면 O(N^2)이 나올테지만, 투포인터를 이용해 start 포인터와 end 포인터를 조정해가면서 구간합을 구하면 O(N)의 시간복잡도가 걸린다.

start 포인터가 ++되면 부분배열의 합이 감소되고,
end 포인터가 ++되면 부분배열의 합이 증가된다.

이 점을 수들의 합5 문제에 적용하여 풀면 다음과 같다.

1. start, end 포인터 설정. start, end=0 초기화
2. start 포인터가 N이 되기 전까지 반복
   2-1. start 포인터 증가시키면서 현재 부분합 구하기
   a. 현재 부분합 < N 이면 탈출
   b. 현재 부분합 == N 이면 정답 +1
   2-2. end 포인터 증가시키면서 현재 부분합 구하기
   a. 현재 부분합 > N 이면 탈출
   b. 현재 부분합 == N 이면 정답 +1

풀이

💬 투포인터 버전

import java.io.*;

public class Main_2018_2 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
	
		int start=0, end=0; //투포인터 설정
		int sum=0, cnt=0; //sum: 합, cnt: 가지수(정답)
		while(start<=N) {
			while(++end<=N) { //end 증가
				sum += end; //부분합을 증가
				if(sum>=N) {
					if(sum==N) cnt++;
					break;
				}
			}
			while(++start<=N) { //start 증가
				sum -= start; //부분합을 감소
				if(sum<=N) {
					if(sum==N) cnt++;
					break;
				}
			}	
		}
		System.out.println(cnt);
	}
}

💬 원본

import java.io.*;
// 5분
public class Main_2018 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int cnt=0; //가지수(정답)
		for(int i=1;i<=N;i++) { //시작
			int sum=0;
			for(int j=i;j<=N;j++) { //시작점부터 순차적으로 더하기
				sum +=j;
				if(sum>N)
					break;
				else if(sum==N) {
					cnt++;
					break;
				}
			}
		}
		System.out.println(cnt);
	}
}

🌟 비슷한 유형의 문제들
2003 : 수들의 합
1644 : 소수의 연속합
1806 : 부분합
2230 : 수 고르기
1484 : 다이어트
2038 : 골룽 수열
2531 : 회전 초밥
2096 : 내려가기
2293 : 동전1

참고
투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)