[파이썬, 자바] 백준 23848 : 등비수열의 합 (골드3)

[파이썬, 자바] 백준 23848 : 등비수열의 합 (골드3)

• https://www.acmicpc.net/problem/23848

---

풀이

방향성 생각

• 10^12 -> 최대 공비 10^6 -> O(N)으로 풀이
  • 항이 3개 이상이어서 r^3 = 10^12로 풀면 10^4까지 줄일 수 있다고 생각했는데, N**(1/3)까지 줄일 수 있다고 생각했는데 안되는듯? 항 개수가 부족해서 답이 안될거같았는데...
• 구간합 구하기 -> 누적합 사용
• 누적합의 길이가 가장 긴 2의 경우, 10^12 = 2^40이라 잡으면 누적합 리스트의 길이는 최대 약 40
• 투포인터로 구간길이가 3 이상인 구간합이 N의 약수인 경우 찾기.
  • 구간합 * a(scaling factor?) = N이므로 N/a == N//a이면 조건 만족
  • 지금 보니까 나머지가 0이면 되는듯
• cumsum의 경우도 구간 길이가 3이 안나오는 경우들이 있는데 이러한 경우도 쳐내면 더 시간 줄일 수 있을 듯

 

---

파이썬

def solution():

    N = int(input())

    for n in range(2,int(N**0.5)+1):

        cumsum = [0,1] 
        while cumsum[-1] < N:
            cumsum.append(cumsum[-1] + n**(len(cumsum)-1))

        if len(cumsum) < 4:
            continue

        for l in range(len(cumsum)-3):
            for r in range(l+3, len(cumsum)):
                diff = cumsum[r] - cumsum[l]
                if N%diff == 0:
                    print(r-l)
                    print(*[(N//diff)*n**i for i in range(l,r)])
                    return 

                elif diff > N:
                    break
    print(-1)

solution()

---

자바

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());
        solution(N);
    }

    public static void solution(long N) {
        for (int n = 2; n <= (int) Math.sqrt(N); n++) {
            List<Long> cumsum = new ArrayList<>();
            cumsum.add(0L);
            cumsum.add(1L);

            while (cumsum.get(cumsum.size() - 1) < N) {
                cumsum.add(cumsum.get(cumsum.size() - 1) + (long) Math.pow(n, cumsum.size() - 1));
            }

            if (cumsum.size() < 4) {
                continue;
            }

            for (int l = 0; l < cumsum.size() - 3; l++) {
                for (int r = l + 3; r < cumsum.size(); r++) {
                    long diff = cumsum.get(r) - cumsum.get(l);
                    if (N % diff == 0) {
                        System.out.println(r - l);
                        for (int i = l; i < r; i++) {
                            System.out.print((N / diff) * (long) Math.pow(n, i) + " ");
                        }
                        System.out.println();
                        return;
                    } else if (diff > N) {
                        break;
                    }
                }
            }
        }
        System.out.println(-1);
    }
}

• 10**12라서 int 대신 long 써주기.
• math.pow에서 long으로 타입 캐스팅해주기.

---

코멘트

• a * (r^(n-1))에서 a=1인 경우만 생각해서 보자마자 풀이 떠오른거에 비해 좀 걸렸다.