[BaekJoon] 17206번 : 준석이의 수학 숙제 (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 준석이의 수학 숙제 입니다.

17206번: 준석이의 수학 숙제

🧑🏻‍💻 문제 풀이

준석이의 수학문제는 

특정한 숫자 N을 입력 받으면 특정한 숫자 N 아래 존재하는 모든 3의 배수와 7의 배수를 더한 값을 구하는 문제입니다.

 

문제의 수는 최대 10만개 / 입력 받는 자연수의 크기는 최대 8만으로

그냥 반복문을 돌면서 3의 배수와 7의 배수를 구하고자하면 시간초과가 걸릴 수도 있는 문제입니다.

 

저는 1 ~ N 까지의 합을 구하는 공식인 

$$\sum_{n=1}^{10}n = \frac{n * (n+1)}{2}$$

위 공식을 활용했습니다.

 

위의 공식을 활용하여

N 이하의 x 배수의 총 합은 아래오 같이 만들어보았습니다.

$$answer = \frac{n * (n+1)}{2} * x$$

 

이를 코드로 구현하면 아래와 같습니다.

def calculate_sum_all_numbers(n, x):
    return n * ( n + 1 ) // 2 * x

위 공식의 n에 각각 아래의 값을 넣어 주었습니다.

- N 이하의 3의 배수의 총 합을 구할때는 n에 N // 3

- N 이하의 7의 배수의 총 합을 구할때는 n에 N // 7

multiple_of_3_num = N // 3
multiple_of_7_num = N // 7

sum_num_3 = calculate_sum_all_numbers(
    n=multiple_of_3_num, x=3
)

sum_num_7 = calculate_sum_all_numbers(
    n=multiple_of_7_num, x=7
)

여기서 생각해보면! 3의 배수와 7의 배수의 합 중에 3과 7의 최소공배수인 21의 배수는 두번씩 더해지므로 

21의 배수의 총합을 한번 빼주어야 하므로 21의 배수의 총합도 하나 구해둡니다.

multiple_of_21_num = N // 21

sum_num_21 = calculate_sum_all_numbers(
    N=multiple_of_21_num, multiple_num=21
)

여기까지 구한 값들로 정답을 구합니다.

$$answer = 3의 배수의 총합 + 7의 배수의 총합 - 21의 배수의 총합$$

answer = sum_num_3 + sum_num_7 - sum_num_21

전체 코드는 아래를 참고해주세요.

🧑🏻‍💻 코드 ( Solution )

def calculate_sum_all_numbers(N, multiple_num):
    return N * ( N + 1 ) // 2 * multiple_num


def solution(problem):
    multiple_of_3_num = problem // 3
    multiple_of_7_num = problem // 7
    multiple_of_21_num = problem // 21
    
    sum_num_3 = calculate_sum_all_numbers(
        N=multiple_of_3_num, multiple_num=3
    )
    
    sum_num_7 = calculate_sum_all_numbers(
        N=multiple_of_7_num, multiple_num=7
    )
    
    sum_num_21 = calculate_sum_all_numbers(
        N=multiple_of_21_num, multiple_num=21
    )
    
    return sum_num_3 + sum_num_7 - sum_num_21
    
    

def junseok_math_homework(problem_list):
    answer_list = []
    
    for problem in problem_list:
        answer = solution(problem=problem)
        
        answer_list.append(answer)
        
    return answer_list


def print_answer(answer):
    for ans in answer:
        print(ans)
        
        
if __name__ == "__main__":
    N = int(input())
    problem_list = list(map(int, input().split()))
    
    answer = junseok_math_homework(
        problem_list=problem_list
    )
    
    print_answer(answer=answer)

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07