[BOJ 1024] 수열의 합(Java, 단순한 풀이)

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

1024번: 수열의 합

 

이 문제는 2가지 방법으로 풀이를 작성하겠다.

 

 

# 풀이1(직관적이나 시간복잡도가 큼).

 

 

1. 길이가 L부터 100까지 탐색을 한다. While문 내에서 합을 L만큼 더해가면서, 합이 N을 만들 수 있는 모든 수를 탐색한다.

 

 

 

2. 합이 N이라면, 정답을 출력한다.

 

---

해설코드(Java).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] sArr = br.readLine().split(" ");
        long N = Long.valueOf(sArr[0]);
        long L = Long.valueOf(sArr[1]);
        boolean flag = true;
        
        for(long i = L; i <= 100 && flag; i++){
            long sum = (i * (i - 1)) / 2;
            long idx = 0;
            
            while(true){
                if(sum == N){
                    for(long k = 0; k < i; k++)
                        bw.write(idx + k + " ");
                        
                    flag = false;
                    break;
                }
                
                sum += i;
                idx += 1;
                
                if(sum > N)
                    break;
            }
        }
        
        if(flag)
            bw.write("-1");
            
        bw.write("\n");
        bw.flush();
    }
}

---

# 풀이2(시간복잡도가 낮음).

 

 

1. N을 만드는 방식을 우선 이해한다. 예를 들어, 1 2 3 4 5와 1 2 3 4를 생각해보자. 두 수를 선택한 것은, 짝수와 홀수의 경우를 모두 보기 위함이다.

* 1 2 3 4 5 = 15일 때, 15 / 5 = 3, 3은 해당 리스트에 들어간다. 3일 때, 처음 시작하는 수는 3 - (길이 - 1 / 2)이다.

* 1 2 3 4 = 10일 때, 10 / 4 = 2, 2도 해당 리스트에 들어간다. 2일 때, 처음 시작하는 수는 2 - (길이 - 1 / 2 )이다.

* 어떤 수로 시작해도, 위의 경우는 모두 성립하므로 일반적인 식을 세울 수 있다.

 

 

 

2. N / L과 길이를 통해서 어떤 수로 시작하는지 값을 찾고, 합을 구해서 N과 같은지 판별해주면 된다. 

* 1부터 시작한다면 간단히, L * (L + 1) / 2로 값을 구할 수 있지만, 특정한 수자 X부터 시작한다면,

(X + X - L - 1) * L / 2로, 값을 구해주면 된다. 즉, (처음 시작하는 수 + 끝나는 수) * 길이 / 2 이다.

 

---

해설코드(Java).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] sArr = br.readLine().split(" ");
        long N = Long.valueOf(sArr[0]);
        long L = Long.valueOf(sArr[1]);
        boolean flag = true;
    
        while(L <= 100){
            long start = N / L - (L - 1) / 2;
            if(start < 0)
                break;
                
            if(N == (start * 2 + L - 1) * L / 2){
                for(long i = 0; i < L; i++)
                    bw.write(start + i + " ");
                flag = false;
                break;
            }
            
            L += 1;
        }
        
        if(flag)
            bw.write("-1");
            
        bw.write("\n");
        bw.flush();
    }
}