[Java] 태민이의 취미

문제 설명

태민이는 주사위를 수집하는 취미를 가지고 있습니다. 주사위의 모양과 색깔은 각기 다르며, 크기 또한 다릅니다. 태민이는 지금까지 모은 N개의 주사위가 너무 난잡하게 보관해놓고 있어서 정리를 결심했습니다. 그래서 우선 N개의 주사위를 크기 순서대로 정리해보려고 마음 먹었습니다.

그렇게 주사위를 순서대로 정렬시켜보니 각 변의 길이가 1부터 N까지 모두 있는 것을 알게되었습니다. 이 사실이 매우 신기했던 태민이는 이 주사위들의 부피의 합은 어떻게 될지 궁금해졌습니다. 태민이가 현재 가지고 있는 모든 주사위의 부피의 합은 얼마일까요? 태민이의 궁금증을 풀어주세요!

입력

첫 줄에 정수 N이 주어집니다. (단, ))

출력

변의 길이가 1부터 N까지인 주사위들의 부피의 합을 출력합니다. 이때, 수가 너무 커질 수 있으므로 1000000007로 나눈 나머지를 출력합니다.

입/출력 예시

입력	출력
10	3025
37	494209
5555	140937120
8764891	831853577

Thinking 1

import java.io.*;

public class Goorm49094 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long answer = 0L;
        int lastWidth = Integer.parseInt(br.readLine());
        for (int i = 1; i <= lastWidth; i++){
            int area = (i * i) % 1000000007;
            int volume = (area * i) % 1000000007;
            answer += volume;
            answer %= 1000000007;
        }

        System.out.println(answer);
    }
}

• 채점결과
  • 20/100

Thinking 2

import java.io.*;

public class Goorm49094 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long answer = 0L;
        long lastWidth = Integer.parseInt(br.readLine());
        for (int i = 1; i <= lastWidth; i++){
            long area = (i * i) % 1000000007L;
            long volume = (area * i) % 1000000007L;
            answer += volume;
            answer %= 1000000007;
        }

        System.out.println(answer);
    }
}

• 채점결과
  • 30/100

Thinking 3

import java.io.*;

public class Goorm49094 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long answer = 0L;
        long lastWidth = Integer.parseInt(br.readLine());
        for (long i = 1L; i <= lastWidth; i++){
            long area = (i * i) % 1000000007L;
            long volume = (area * i) % 1000000007L;
            answer += volume;
            answer %= 1000000007;
        }

        System.out.println(answer);
    }
}

• 채점결과
  • 60/100

시간초과를 잡고자 어떻게 할까 계속 고민했다. 처음에 생각했을 때는 무조건 반복문을 돌아야 한다고 생각했는데, 반복문 외에는 시간초과가 날 이유가 없는 것 같았다. 반복문을 돌리지 않고 해당 로직을 수행할 방법을 고민했다. n³의 합을 구하는 일반항 공식을 사용해서 반복문을 돌지않고 로직을 작성해보자.

완성 코드

import java.io.*;

public class Goorm49094 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long num = Integer.parseInt(br.readLine());
        long sum = num * (num + 1) / 2 % 1000000007L;
        long answer = sum * sum % 1000000007L;

        System.out.println(answer);
    }
}

알고리즘은 수학적 사고가 필요하구나..!

---

문제 출처