백준 17206 준석이의 수학숙제[Java]

https://www.acmicpc.net/problem/17206

풀이

예전에 풀었던 기록이 있어서 확인해봤더니 시간초과였다. 단순히 숫자를 입력받을 때마다 for문을 돌려서 누적합을 구해 출력하면, 시간초과가 날 수 밖에 없다. 설명에서 "문제는 중복될 수 있다."라는 말에서 힌트를 얻어 숫자를 입력받기 전 미리 답을 구해서 배열에 저장한 다음 출력하는 방법을 사용했다.

코드

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));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] answer = new int[80001];
        answer[10] = 25;
        int tmp = 25;
        for (int i = 11; i <= 80000; i++) {
            if (i % 3 == 0 || i % 7 == 0) {
                answer[i] = tmp + i;
                tmp = answer[i];
            }
            else
                answer[i] = tmp;
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(st.nextToken());
            sb.append(answer[n] + "\n");
        }
        System.out.println(sb);
    }
}

• answer[N] : N 이하의 3 또는 7의 양의 배수를 모두 더한 값