006. 수들의 합5(백준2018번)

문제

문제 분석하기

제한시간 2초 = 2억번의 연산안에 끝나야한다.

$N$ 의 최댓값 = 10,000,000

$O(NlogN)$ = 10,000,000 -> $10000000log_210000000$ = 약 230,000,000 (2억3천)
위 시간복잡도는 제한시간을 넘어가므로 위 시간복잡도보다 좀 더 작은 시간복잡도를 사용해야한다. $O(N)$ or $O(log_2N)$ or $O(1)$

$O(N)$ 의 시간복잡도를 가진 투 포인터를 사용해보자

손으로 풀어보기

투 포인터

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어있는 두 리스트의 합집합에도 사용된다.
• 병합정렬의 기초가 되기도 한다.

위 이미지는 투포인터를 이용해 12(N) 를 연속된 자연수의 합으로 나타내는 가지수를 구하는 과정을 보여준다.

어떠한 이동법칙이 보일것이다. (이미지 안에 적어 두었다ㅎ)

• N > sum(연속된 자연수의 합)
  end_index++;
  sum += end_index;

• N < sum
  sum -= start_index;
  start_index++;

• N == sum
  end_index++;
  sum += end_index;

슈도코드 작성하기

long N = 입력 받기

사용 변수들 초기화(long count, startIdx, endIdx, sum;)

while(endIdx != N) {
	if(sum == N){
		count 증가
		endIdx 증가
		sum 변경
	}else if(sum > N) {
		sum 변경 
		startIdx 증가
	}else if(sum < N) {
		endIdx 증가
		sum 변경
	}
}
count 출력

위 처럼 슈도 코드를 작성하고 나면 궁금증이 하나 생긴다.

if문 안의 증가/변경 코드들의 순서도 상관이 있을까?
sum == N 일때와 sum < N 일때는 endIdx를 증가시키고 sum을 변경하는데
sum > N 일때에는 sum을 먼저 변경하고 startIdx를 증가 시키고있다.

sum > N 일때 startIdx를 먼저 증가시키고 sum을 변경하면 답이 변경되어 출력된다.
왜일까?

sum > N 일 때 연속된 자연수에서 start_index를 삭제해야한다.
만약 위 코드와 다르게 start_index를 증가 시키고 sum을 변경 한다면 start_index를 삭제하는 효과를 기대하기 어렵다.

코드 구현하기

public class Main {  
  
    public static void main( String[] args ) throws IOException {  
       BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );  
       BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );  
       StringTokenizer st = new StringTokenizer( br.readLine( ) );  
  
       long num = Integer.parseInt( st.nextToken() );  
       long count, startIdx, endIdx, sum;  
       count = startIdx = endIdx = sum = 1;  
  
       while ( endIdx != num ) {  
          if ( sum == num ) {  
             count++;  
             endIdx++;  
             sum += endIdx;  
          } else if ( sum > num ) {  
             sum -= startIdx;  
             startIdx++;  
          } else {  
             endIdx++;  
             sum += endIdx;  
          }  
       }  
  
       bw.write( count + "\n" );  
       bw.flush();  
    }  
  
} // end