백준 - 수열의 합(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/1024

[문제 설명]

1인 등차를 가진 배열의 합이 N이고 길이가 N이상인 것을 찾으시오

[접근 방법]

등차수열식으로 첫항을 유도하기

a는 첫항, d는 등차, n은 수열의 순서라고 할 때

An = a+(n-1)d

Sn(1번부터 n번까지 수열의 총합) = (첫항+끝항)/2*전체개수 = ((2a+(n-1)d)/2)*n == N

 

현재 우리에게 주어진 조건은 N과 L<=n<=100이라는 것과 배열의 값이 연속적(등차가 1)이라는 것.

=> N = ((2a+(n-1))/2)*n

=> a에 대한 식으로 만들자 (2a+n-1)*n = 2N => (2a+n-1) = 2N/n => 2a = 2N/n-n+1

=> a = N/n - n/2 + 1/2 =>N/n+(1-n)/2 => a = (2N+n-n^2)/2n

=> 첫항은 0이상이므로 a의 값이 0 이상인 정수 값이 나오면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static Set<Integer> cardSet = new HashSet<>();
    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());

        int n = L;
        int a = 0;
        while (n <= 100) {
            int child = 2*N+n-n*n;
            int parent = 2*n;
            if (child % parent == 0) {
                a = child/parent;
                if (a >= 0) {
                    break;
                }
            }
            n++;
        }

        if (n == 101) {
            System.out.println(-1);
            return;
        }
        for (int i = 0; i < n; i++) {
            System.out.println(a+i);
        }
    }
}

[느낀점]

수학이 알고리즘 풀 때 쓸모가 있긴 하구나.

+ 변수명 최대한 안헷갈리게 두자.

++ 최악의 경우 헷갈리는 변수명을 짓더라도 명확하게 이게 뭐하는 변수인지 명시해두면 헤메지 않는다.