백준 - [ 1024번: 수열의 합 ]

문제

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

입력

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

출력

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

예제 입력 1 

18 2

예제 출력 1 

5 6 7

예제 입력 2 

18 4

예제 출력 2 

3 4 5 6

 

 
 

---

규칙 찾는 데 시간을 많이 쓴 문제이다.
 
우선 받아온 수의 홀수/짝수 여부에 따라서 리스트의 개수가 될 수 있는 수를 각각 odd, even 리스트에 담았다. 
수를 연속된 리스트의 합으로 나타내야 하므로, 홀수의 경우에는 홀수가 홀수개 있어야 하고, 짝수의 경우에는 홀수가 짝수개 있어야 한다.
 
내가 연속된 리스트를 찾은 방식은 아래와 같다.

1. 연속된 리스트의 합으로 나타낼 때 0부터 시작해서 리스트의 길이까지 연속된 수를 만들고, (ex. 리스트의 길이가 3이면 0-1-2, 길이가 5이면 0-1-2-3-4)
2. 연속된 수의 합을 N에서 빼고
3. 리스트의 길이만큼 나눈 값을 각각의 리스트 수에 더해주면 된다.

말로 설명하려니 잘 못하겠는데.. 예를 들어 N이 18이고, 리스트의 길이가 3이라고 가정했을 때 1. 우선 만들어진 연속된 수는 0-1-2 이고,  2. 연속된 수의 합(0+1+2)을 N에서 빼면 15가 된다. 3. 여기서 리스트의 길이 3만큼 나누면 5가 나오고, 이 값을 각각 리스트에 더해주면 5-6-7로 연속된 리스트로 나타낼 수 있다.
 
이렇게 구하려니 홀수의 경우에는 리스트의 개수가 4의 배수가 될 수 없고(홀+짝+홀+짝 이므로 합이 무조건 짝수가 됨)
짝수의 경우에는 리스트의 개수가 4의 배수+2가 될 수 없었다. (홀+홀+홀+짝+짝+짝 ... 홀+홀+홀+홀+홀+짝+짝+짝+짝+짝 이렇게 홀수 개수가 홀수이므로 합이 무조건 홀수가 됨)
이를 이용해 odd와 even 리스트를 채워주었다.
 
그리고 N의 홀수/짝수 여부에 따라  odd/even 리스트를 돌면서 해당 개수 만큼 연속된 수의 합으로 나타낼 수 있는지 확인해주었다.
 

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        List<Integer> odd = new ArrayList<>(); // 홀수에서 리스트 개수 후보 2 3 _ 5 6 7 _ 9 ...
        List<Integer> even = new ArrayList<>(); // 짝수에서 리스트 개수 후보 3 4 5 _ 7 8 9 _ ...
        for (int i = 2; i <= 100; i++) {
            if (i % 4 != 0) {
                odd.add(i);
            }
            if ((i - 2) % 4 != 0) {
                even.add(i);
            }

        }

        List<Integer> tmpList = N % 2 == 0 ? even : odd;
        String answer = "";
        for (int i = 0; i < tmpList.size(); i++) {
            int len = tmpList.get(i); // 검토할 리스트 개수
            if (len < L) continue;

            int[] num = new int[len]; // 0부터  len-1까지 숫자 담을 배열
            int sum = 0;
            for (int j = 0; j < len; j++) {
                num[j] = j;
                sum += num[j];
            }

            int tmp= N-sum;
            if (tmp % len != 0) { // 안 나눠떨어지면 못 구함
                continue;
            } else if (tmp < 0) { // 음이 아닌 정수 리스트여야 함
                break;
            } else {
                for (int digit : num) {
                    answer += digit + tmp / len + " ";
                }
                break;
            }
        }

        if (answer.equals("")) {
            answer = "-1";
        }

        bw.write(answer);
        bw.flush();
        bw.close();
        br.close();
    }

}

 
 

---