[구현/수학] 백준 1834 나머지와 몫이 같은 수

[ Contents ]

1. 문제 (링크 참조)

1834번: 나머지와 몫이 같은 수

N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

www.acmicpc.net

N으로 나눈 나머지와 몫이 같은 수를 구하는 문제입니다.

완전탐색으로 모든 수를 N으로 나누고 나머지와 몫을 비교하면 시간 초과가 날 뿐더러, 그 끝을 어디로 해야하는지 알 수도 없습니다. 그 대신에 나머지와 몫이 같은 수를 계산할 수는 있습니다.

N으로 나눈 몫은 0부터 무한대까지 가능하지만, 나머지는 0 ~ N-1까지로 한정되어 있습니다. 즉, 몫과 나머지가 같은 수는 N개 밖에 없습니다. (몫과 나머지가 0 ~ N-1인 수)

# 입력
N = int(input())

# N까지 나머지와 몫이 같은 수 합하기
res = 0
for i in range(N):
    res += N*i + i  # 나머지와 몫이 같은 수
print(res)

0부터 N-1까지 나머지와 몫이 같은 수를 구해줍니다. 몫이 i이므로 N*i해준 뒤, 나머지 i를 더해주면 됩니다.