[코딩테스트/백준 알고리즘] 1024번 : 수열의 합 (Java, 자바 풀이)

문제

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

1024번: 수열의 합

---

문제 설명

---

문제 풀이

어떤 수 x가 있을 때, k개의 연속적인 합을 구하는 식을 만들면 아래의 표와 같다.

k	k개의 연속인 합	식
1	x	x
2	x + (x + 1)	2x + 1
3	x + (x + 1) + (x + 2)	3x + 3
4	x + (x + 1) + (x + 2) + (x + 3)	4x + 6
5	x + (x + 1) + (x + 2) + (x + 3) + (x + 4)	5x + 10
...	...	...
k	x + (x + 1) + (x + 2) + ... + (x + k - 1)	kx + (1 + 2 + ... + k - 1)

 

이를 이용해서 n = 18, l = 2인 예제를 풀어보자. 일차방정식을 이해했다면 쉽게 해결할 수 있다.

 

ㅣ = 2일 때 (불가능)

• 2x + 1 = 18
• 2x = 17
• x = 8.5

ㅣ = 3일 때(가능)

• 3x + 3 = 18
• 3x = 15
• x = 5

따라서 x = 5일 때 연속된 세 수는

x, x + 1, x + 2 ➡️ 5, 6, 7 임을 알 수 있다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();	//n
        int l = sc.nextInt();	//l
        int t = 0;	//상수항

        for(int i = 0; i < l; i++) {
            t += i;
        }

        while(true) {
            if((n - t) % l == 0 && (n - t) / l >= 0) {
                int div = (n - t) / l;	//몫

                for(int i = 0; i < l; i++) {
                    System.out.printf("%d ", div + i);
                }
                return;
            }
            else {
                t += l;
                if(n - t < 0 || ++l > 100) {	//리스트의 길이가 100보다 긴 경우
                    System.out.println("-1");
                    return;
                }
            }
        }
    }
}