[백준] 1024번. 수열의 합(JAVA)

문제

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

---

풀이(12분)

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());

        ArrayList<Integer> list = new ArrayList<>();

        int cnt = 0;
        int sum = 0;
        for(int i = 0 ; i < n; i++){
            if(sum + i < n){
                sum += i;
                cnt++;
            }
        }

        for(int i = l; i <= cnt+1; i++){
            int minus = (i-1)*i/2;
            if((n - minus) % i == 0){
                for(int j = 0; j < i; j++){
                    list.add((n - minus)/i + j);
                }
                break;
            }
        }

        if(list.size() == 0 || list.size() > 100){
            System.out.println(-1);
            return;
        }

        for(int x : list){
            System.out.print(x + " ");
        }

    }
}

 

연속된 수열의 합을 생각하면(연속이기 때문에 등차수열이라고 생각하자.) 고등학교 시절에 풀어본 문제들을 모두 기억할 것이다.

 

예를 들어 연속된 세개의 수열의 합을 구하는 문제에서  a-d, a, a+d 라고 두어 수열의 합이 3a로 간단하게 정리되는 문제들이 있다.

 

하지만 여기선, 연속된 것에 대한 처리를 간단하게 하기 위해 a, a+d, a+2d ... 등으로 두어 문제를 풀었다.

 

길이가 최대 몇까지 될 수 있는지 먼저 구한 뒤에, l부터 최대 길이까지만 반복하여 구하는 방식이다.