[2018] 수들의 합 5

✔ 수들의 합 5

[백준 2018]

문제 분석하기

시간 제한은 2초이지만 N의 최댓값은 10000000으로 매우 크게 잡혀 있으므로 O(n)의 시간 복잡도 알고리즘이 필요

이런 경우 자주 사용하는 방법이 투 포인터

시작 인덱스와 종료 인덱스를 투 포인터로 지정하여 연속된 수를 표현하도록 문제에 접근

손으로 풀어보기

1. 입력받은 값을 N에 저장한 후 사용할 변수를 모두 초기화하고, 결과 변수는 N 하나만 사용하는 경우가 있으므로 1로 초기화
2. 투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우를 수를 구함
   • sum > N : sum = sum - start_index; start_index++;
   • sum < N : end_index++; sum = sum + end_index;
   • sum == N : end_index++; sum = sum + end_index; count++;

슈도코드 작성하기

N 변수 저장
사용 변수 초기화(count = 1, start_index = 1, end_index = 1, sum = 1)
while(end_index != N) {
    if(sum == N) count 증가, end_index 증가, sum값 변경
    else if(sum > N) sum값 변경, start_index 증가
    else if(sum < N) end_index 증가, sum값 변경
}
count 출력하기

코드 구현하기

/**
 * 2018) 수들의_합_5
 */
public class D006_2018 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N 변수 저장
        int N = sc.nextInt();
        // 사용 변수 초기화
        int count = 1;
        int start_index = 1;
        int end_index = 1;
        int sum = 1;
        while (end_index != N) {
            // 현재 연속 합이 N과 같은 경우
            if (sum == N) {
                // count 증가, end_index 증가, sum값 변경
                count++;
                end_index++;
                sum = sum + end_index;
                // 현재 연속 합이 N보다 더 큰 경우
            } else if (sum > N) {
                // sum값 변경, start_index 증가
                sum = sum - start_index;
                start_index++;
                // 현재 연속 합이 N보다 작은 경우
            } else {
                // end_index 증가, sum값 변경
                end_index++;
                sum = sum + end_index;
            }
        }
        // count 출력하기
        System.out.println(count);
    }
}