백준 1024 : 수열의 합

 

문제 바로 가기

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

 

접근 방법

연속된 수의 합을 구하는 방법에 대한 규칙을 찾는 것이 핵심이다.

연속된 수의 합을 구하는 방법은 다양한 방법을 사용할 수 있겠지만, 나는 가장 작은 수와 가장 큰 수를 더해서 연속된 갯수만큼 곱한 후 2로 나누는 방법을 사용했다.

예를 들어서 `3, 4, 5, 6, 7` 이라는 연속된 숫자가 있다고 생각해보자.

가장 작은 수와 가장 큰 수를 모두 더해보면 아래와 같이 될 수 있다.

`3 + 7 = 10`

`4 + 6 = 10`

`5 + 5 = 10`

`6 + 4 = 10`

`7 + 3 = 10`

`10 \times 5 = 50` 은 3부터 7까지 합한 값의 2배가 된다. 따라서 2로 나누어주면 3부터 7까지 연속된 수의 합인 25가 나온다.

 

Step 1. 수학적 접근

위의 아이디어를 활용하면 문제 풀이에 필요한 수식을 구할 수 있다.

연속된 정수의 합은 N이 되어야 하고,  시작하는 숫자가 `a` 이면서 연속된 수의 길이가 `L` 이라면 `a, a+1, a+2, ..., a + (L-1)`과 같이 연속된 수를 표현할 수 있다.

그리고 이렇게 연속된 수의 합을 위에서 다룬 특징을 활용하면 아래와 같이 정리할 수 있다.

`N = a + (a + 1) + (a + 2) + ... + (a + (L -1)) = \frac {L} {2} \times (2a + (L - 1))`

 

Step 2. 첫 번째 숫자인 a 구하기

결국에는 첫 번째 숫자를 구하고, 1씩 증가하면서 범위 내에 숫자를 출력해야 한다. 따라서 우리가 현재 구해야 하는 것은 `a`이고, `a`는 위에서 구한 식을 변형해서 구할 수 있다.

`2N = L \times (2a + (L - 1))`

`\frac {2N} {L} = 2a + (L - 1)`

`2a = \frac {2N} {L} - (L - 1)`

`a = \frac {\frac {2N} {L} - (L - 1)} {2}`

최종적으로 a를 위와 같은 식을 통해서 구할 수 있지만, 너무 지저분하기 때문에 분자와 분모에 L을 곱해서 사용하겠다.

`a = \frac {2N - L(L-1)} {2L}`

이렇게 분모와 분자를 정리하면 코드를 작성할 때 아래와 같이 깔끔하게 변수로 정리해서 활용할 수 있게 된다.

int numerator = 2 * N - l * (l - 1);	// 분자
int denominator = 2 * l;	// 분모

 

Step 3. 반복문으로 가능한 L의 값을 구하기

L의 최소 값은 2이고, 최대 값은 100이다.

주어진 범위 내에서 L값을 하나씩 증가하면서 a를 계산할 수 있다. 이때, a가 음이 아닌 정수일 때까지 반복한다.

분자를 분모로 나누었을 때 나누어 떨어지는지 확인해서 a가 정수인지 확인하고, a가 음이 아닌 정수인지 확인한다.

만약 조건에 해당되는 a를 찾았다면 l의 길이까지 반복문을 돌면서 결과를 출력하면 된다.

이 부분을 코드로 구현한다면 아래와 같이 작성할 수 있다.

for (int l = L; l <= 100; l++) {
    int numerator = 2 * N - l * (l - 1);
    int denominator = 2 * l;

    if (numerator % denominator == 0) {
        int a = numerator / denominator;
        if (a >= 0) {
            found = true;
            for (int i = 0; i < l; i++) {
                bw.write((a + i) + " ");
            }
            break;
        }
    }
}

 

Step 4. 예외 처리 및 전체 코드 작성

유효한 수열을 찾지 못했다면 -1을 반환하는 조건이 포함된 전체 코드는 아래와 같이 작성할 수 있다.

import java.io.*;
import java.util.*;

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());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        boolean found = false;

        for (int l = L; l <= 100; l++) {
            int numerator = 2 * N - l * (l - 1);
            int denominator = 2 * l;

            if (numerator % denominator == 0) {
                int a = numerator / denominator;
                if (a >= 0) {
                    found = true;
                    for (int i = 0; i < l; i++) {
                        bw.write((a + i) + " ");
                    }
                    break;
                }
            }
        }

        if (!found) {
            bw.write("-1");
        }

        br.close();
        bw.close();
    }
}