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

문제

풀이

합이 N이면서 연속된 수열의 길이가 적어도 L인 수열을 구해야 한다.

 

처음에 공식을 바로 사용하길래 이 공식이 무슨 공식인줄 잘 이해가 안되었다. 근데 연속된 수의 합이라서 공차가 1인 등차수열을 생각해서 해당 공식을 찾아보았다.

 

등차 수열의 합 공식

a가 첫 항, n이 항의 갯수 d가 공차(여기서는 1)

a를 구하는 방법은 합인 N이 주어졌을 때 그 몫(N/L)의 앞뒤 수를 (L-1)/2만큼 더하거나 뺐을 때 연속된 수가 나온다.

(N/L) - (L-1)/2를 하면 몫을 기준으로 연속된 수의 가장 처음 수를 구하는 식인데 이게 음수이면 안된다. 

그리고 이 수가 등차수열 합 공식의 a에 해당한다.

 

연속하는 처음 수를 L의 개수만큼 더한 결과가 N과 같으면 L길이 만큼 처음 수 부터 출력

같지 않으면 L++로 L값을 증가

L값이 100이 넘어도 -1 출력

정답 코드

package com.baekjoon.math.p1024;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();
        int L = sc.nextInt();

        /**
         * N이 주어졌을 때 자연수(L)로 나누게 되면 그 몫(N/L)의 앞뒤 수를 (L-1)/2 만큼 더하거나 뺏을 때 연속된 수가 나온다.
         * 연속된 수의 가장 처음 수 -> N / L - (L - 1) / 2
         */
        while (true) {
            int min = N / L - (L - 1) / 2;

            if (min < 0 || L > 100) {
                sb.append(-1);
                break;
            }

            int sum = L * (min * 2 + (L - 1)) / 2;

            if (sum == N) {
                for (int i = 0; i < L; i++) {
                    sb.append((min + i) + " ");
                }
                break;
            }

            L++;
        }

        System.out.println(sb);
        sc.close();
    }
}

 

 

참고

https://mathbang.net/607#gsc.tab=0

https://mathbang.net/609#gsc.tab=0