[BOJ] 20743 Bus Numbers

문제 링크

www.acmicpc.net/problem/20743

풀이

$m$의 최댓값이 40만이므로, 어떤 정수 $x^3+y^3$이 40만 이하인 모든 경우에 대해 생성하여 개수를 센다.
그렇게 2개 이상의 서로 다른 방법으로 나타낼 수 있는 수가 우리가 찾는 정답이다.

Java 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int[] cnt = new int[400001];

        for (int i = 1; i * i * i <= 400000; ++i) {
            int rest = 400000 - i * i * i;
            for (int j = i; j * j * j <= rest; ++j) {
                cnt[i * i * i + j * j * j]++;
            }
        }

        int x = Integer.parseInt(in.readLine());
        for (int i = x; i > 0; --i) {
            if (cnt[i] > 1) {
                System.out.println(i);
                return;
            }
        }

        System.out.println("none");
    }
}