BOJ 17206번 - 준석이의 수학 숙제

[백준 온라인 저지 링크]

17206번: 준석이의 수학 숙제

주어진 N 이하의 3 또는 7의 배수의 합을 구하는 문제입니다.

[이렇게 풀면 안돼요]

T = int(input())

a = list(map(int, input().split()))

for elem in a:
    ans = 0
    for i in range(elem + 1):
        if i % 3 == 0 or i % 7 == 0:
            ans += i
    print(ans)

이렇게 코드를 짜면 (최대 10만개의 케이스) * (for문 루프 80000개) 의 제약에 걸리게 되어 시간 초과가 납니다.

따라서 for문을 매 케이스마다 돌리는 방식으로는 해결할 수 없고, 대신 메모이제이션을 활용해 미리 80000까지의 배수의 합을 구한 테이블을 만들고 memo[N] 을 출력하는 방식으로 풀 수 있습니다.

[정답 코드 - Python]

T = int(input())

a = list(map(int, input().split()))
memo = [0] * 80001
ans = 0

for i in range(80001):
    if i % 3 == 0 or i % 7 == 0:
        ans += i
    memo[i] = ans

for elem in a:
    print(memo[elem])

 

카테고리 분류가 "수학" 으로 되어있어서 아무 생각없이 덤볐다가 틀렸는데, DP의 메모이제이션 개념을 활용하기 좋은 문제였습니다!