[BAEKJOON] 1024. 수열의 합(JAVA)

:D 문제

---

문제

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.

Baekjoon

1024번: 수열의 합

 

:D 풀이 방법

---

나는 입력 예제를 통해 아래의 식의 값이 0이면 L만큼의 수열을 구할 수 있다고 두고 문제를 풀었다.

여기서 initValue는 0부터 L-1까지 더한 초기값을 의미한다. 

예를 들어 입력과 같이 N=18이고, L=2일 경우,  (18 - (0+1)) % 2로 계산한다. 계산한 결과가 0이 아님으로 L=2일 때 합이 N인 수열을 구할 수 없다. 그래서 수열을 구할 수 있는 L을 찾을 때까지 L에 1을 증가시켰다.

현재 L=2 임으로 1 증가시켜 L=3으로 설정하고, initValue에 2를 더해 다시 계산을 진행한다. 해당 값을 식에 대입하면 (18 - (0+1+2)) % 3의 결과가 0 임으로 L=3일 때 합이 N인 수열을 구할 수 있다.

 

 

 

:D 작성 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution1024H {
    static int N, L;
    static int[] result; // 결과 순열 저장
    static StringBuilder answer;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        answer = new StringBuilder();

        String input = br.readLine();
        StringTokenizer tokenizer = new StringTokenizer(input, " ");
        N = Integer.parseInt(tokenizer.nextToken());
        L = Integer.parseInt(tokenizer.nextToken());

        int initValue = 0;
        for (int i = 0; i < L; i++) {
            initValue += i;
        }

        int length = L;
        while (true) {
            if ((N - initValue) % length == 0) break;
            initValue += length;
            length++;
        }

        // length 크기 만큼 배열 생성
        result = new int[length];

        // 조건에 만족하는 수열을 찾았는지 여부
        boolean isFound = false;

        // length는 100보다 작은 경우만 가능 함
        if (length <= 100) {

            // 0부터 N까지 length개 만큼 탐색
            for (int i = 0; i <= N; i++) {
                int sum = 0;
                for (int j = 0; j < length; j++) {
                    sum += j + i;
                    result[j] = j + i;
                }

                // length개의 수열의 합이 N과 같고, 수열의 개수가 length보다 크거나 같다면,
                if (sum == N && result.length >= length) {
                    printAnswer();
                    isFound = true;
                    break;
                }
            }
        }

        // 끝까지 찾지 못했다면 -1
        if (!isFound) answer.append(-1);
        
        System.out.println(answer);
    }

    // 출력
    private static void printAnswer() {
        for (int num : result) {
            answer.append(num + " ");
        }
    }
}