[자바] 백준 10504 - 덧셈 (boj java)

문제 : boj10504

 

  24의 경우 7+8+9가 답이다. 대충 봐도 중간 특정 지점에서 시작되는 숫자에 대해, 몇 개의 합인지도 지정되지 않은 상태로 연속되는 양의 정수의 구간을 찾기란 어려워 보인다. 개인적으로 수학이 약해서 정말 어려웠다 ㅠ.

 

  약간 생각을 바꿔서, 그럼 중간부터 시작되지 않고 항상 1부터 시작된다고 해보자. 즉, a까지의 합이라고 하면 1+2+...+a 가 N이라고 하면 어떨까? 이건 상대적으로 쉬워보인다. a는 최대 44720이니깐(44720x44721/2 = 999,961,560 이고, 문제에서 제시된 입력값의 최대치가 10^9 이므로 최대 44720 까지만 보면 된다.), O(44720)으로 찾을 수 있다. 그리고 a를 2부터 44720까지 증가시키면서 확인해보면 '만약 여러 개의 표현이 존재한다면, 가장 짧은 표현을 출력' 부분도 문제없이 처리할 수 있을 것이다.

 

  그럼 이걸로 10 = 1 + 2 + 3 + 4 같은거야 찾을 수 있지만, 24 = 7+8+9 같은걸 어떻게 찾느냐고 할 수 있다. 24를 생각해보자. 3개의 합인 경우 내가 제시한 방법으론 1+2+3이다. 그리고 그 값은 6이고, (24-6)/3 은 6으로 나누어떨어진다. 즉 1+2+3의 각 부분에 +6 씩을 해주면 7+8+9가 된다는 얘기이다. 정리하면 아래의 수식을 만족하는걸 찾아주면 된다(x를 2부터 44720까지 진행하면서 x로 나누어 떨어질때까지). N은 각 테스트케이스마다 입력받은 숫자이다. x(x+1)/2는 1부터 x까지의 합이다. x|z 는 z mod x == 0 이라는 의미이다(z가 x로 나누어떨어짐).

 

  예를들어 24에 대해 f(2)에서 24-2(2+1)/2 = 21 이고 이건 2로 나누어 떨어지지 않으므로 넘어간다. f(3)일 땐 24-3(3+1)/2 = 18이고 이건 3으로 나누어 떨어지므로 18/3 = 6을 기준으로 1+2+3에 더해서 (1+6)+(2+6)+(3+6) = 7+8+9를 출력해주면 된다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static final int SEQ_SUM_LIMIT = 44720;
    private static final int[] sumOfSeq = new int[SEQ_SUM_LIMIT+1];

    private int getAnswer(int n) {
        for (int i = 2; i <= SEQ_SUM_LIMIT; i++) {
            int tmp = n - sumOfSeq[i];
            if (tmp < 0) return -1;
            if (tmp%i==0) return i;
        }
        return -1;
    }
    private void solution() throws Exception {
        for (int i = 1; i <= SEQ_SUM_LIMIT; i++) sumOfSeq[i] = sumOfSeq[i-1]+i;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            int n = Integer.parseInt(br.readLine());
            int answer = getAnswer(n);
            if (answer == -1) {
                sb.append("IMPOSSIBLE").append('\n');
                continue;
            }
            sb.append(n).append(' ').append('=').append(' ');
            int base = (n-sumOfSeq[answer])/answer;
            for (int i = 1; i < answer; i++)
                sb.append(base+i).append(' ').append('+').append(' ');
            sb.append(base+answer).append('\n');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}