[BaekJoon] 백준 1834 나머지와 몫이 같은 수 (Python / 파이썬)

BaekJoon 백준 1834 나머지와 몫이 같은 수 문제는 2,000,000 이하의 자연수 N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 문제이다. 난이도는 Bronze 1이다. 단순한 문제 같지만 N의 크기가 커지면 시간 초과가 날 수 있는 문제이다.

 

BaekJoon 1834 나머지와 몫이 같은 수 문제 정보

출처

- https://www.acmicpc.net/problem/1834

알고리즘 분류

- 수학

난이도

- 브론즈 1 / Bronze 1

 

나머지와 몫이 같은 수 문제 요약

• N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하여 출력한다.
• N은 2,000,000 이하의 자연수이다.
• 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

 

문제 풀이 과정

시간 초과

단순하게 생각하여 몫과 나머지가 같을 때라는 조건문과 반복문을 함께 사용하면 N이 2,000,000까지 있기 때문에 시간제한 2초를 넘겨 시간 초과가 발생한다.

sum = 0
N = int(input())
for i in range(N + 1, N * N):
    if i // N == i % N:
        sum += i
print(sum)

 

그래서 수학적으로 접근하여 몫과 나머지를 다룰 수 있는 검토식을 활용하면 조건문 없이 풀 수 있고, 시간도 줄어든다.

 

A ÷ N = 몫... 나머지 일 때, 검토식은 N X 몫 + 나머지 = A이다.

나머지는 0보다 크고, N보다 작고, 몫 = 나머지 이므로 A = N * i + i (0 <i <N)의 식을 도출할 수 있다.A를 모두 더하여 출력하면 된다.

 

코드 및 설명

sum = 0
N = int(input())
for i in range(1, N):
    sum += N * i + i
print(sum)

---

BaekJoon 백준 1834 나머지와 몫이 같은 수 문제를 파이썬 python으로 풀어보았다. 간단한 문제인 줄 알았지만 수학적으로 접근해야 하는 문제였다. 난이도는 Bronze 브론즈 1이다.