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

문제출처: https://www.acmicpc.net/problem/17206

풀이

그냥 단순히 3또는 7의 배수인 수를 구해서 정답을 구하면 100%시간초과가 뜹니다.

테스트케이스가 최대 10만번인데 입력범위가 최대 8만 까지이므로

T가 10만이고 모든 테스트케이스의 N이 8만인 최악의 경우 최대 80억번 연산을 해야합니다.

따라서 저는 연산 전 미리 10만까지의 수에 대해 배열에 그 값까지의 합을 구해놓고 풀었습니다.

예를들어 N이 49면 temp[49]는 3부터 49까지의 수 중 3또는 7의 배수일 때 그 수들의 합을 미리 저장해서 답만 출력시키게끔 했습니다.

이렇게 하면 최대 연산횟수를 80억번에서 18만번으로 떡락시킬 수 있습니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100001];
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(false);
    int t, temp=0, sum = 0;
    for (int i = 3; i <= 80000; i++)
    {
        if (i % 3 == 0 && i % 7 == 0)
        {
            temp += i;
        }
        else if (i % 3 == 0)
        {
            temp += i;
 
        }
        else if (i % 7 == 0)
            temp += i;
        arr[i] = temp;
    }
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> temp;
        cout << arr[temp] << '\n';
    }
 
}

결과