이 문제는 1000미만의 수 까지 3 혹은 5의 배수인 경우의 수의 합을 구하는 문제입니다.
사실은 결과만 구하자고 한다면... 1~999까지 순회를 돌면서... 3의 배수이거나 5의배수이면 int변수에 더하고 결과를 리턴하면 될 것입니다. 하지만... 알고리즘 측면에서 생각해보면 주어진 숫자가 1000이 아니고 10억정도의 아주 큰 목표값을 가진다면... 어떻게 하실건가요??
아마도 변수형은 Long으로 한다고 하더라도, 오랜시간이 소요될 것 입니다. 또한, Testcase를 여러개 주어진다고 하면 더할나위가 없겠죠??
저는 이렇게 풀어보겠습니다. 1 ~ 10까지 합을 구한다고 했을때... 순차적으로 구하는 방법도 있겠지만... 일정 간격으로 늘어나는 연속된 수의 합은 아래의 방법으로 구할 수 있습니다.
[풀이로직]
- (가장첫번째 숫자 + 가장마지막 숫자) * (그 쌍의 갯수)
물론 전체 갯수가 홀수일 경우 중간값은 추가로 더하는 로직이 필요합니다.
이렇게 연산을 수행한다면... 순회를 돌지않고 단지 수학적인 연산만으로 계산이 가능하게 됩니다. 그렇다면 실질적인 코드는 어떻게 생기게 될까요??
(C++로 하려고 했는데... 얼마전 포맷으로 프로그램이 없어서... 그냥 일단 python으로 진행했습니다.)
def rangeSum(target, divider):
divcnt = (target - 1) // divider
endNo = divider * divcnt
ret = 0
if divcnt == 1:
ret += divider
elif divcnt > 1:
ret += (divider + endNo) * (divcnt >> 1)
if divcnt & 1 and divcnt > 1:
ret += divider * ((divcnt >> 1) + 1)
return ret
if __name__ == '__main__':
tc = int(input())
for t in range(tc):
inputNo = int(input())
Ans = rangeSum(inputNo, 3) + rangeSum(inputNo, 5) - rangeSum(inputNo, 15)
print(Ans)꼭 1000이라는 숫자가 아니고, 사용자가 입력을 통해서 목표를 입력하고, 결과를 출력하도록 작성했습니다.
전체적인 로직은 목표 숫자미만을 기준으로 3, 5, 15일때를 구해서 중복되는 값 (15의 배수)에 대해서는 연산결과에서 빼주었습니다. 또한, 2로 나누었을때 나머지가 0인 경우와 1인 경우에 대해서 분기하는 로직을 구현하였습니다.
이렇게 나온 결과를 제출해보니~!! 무사통과 되었습니다~~!! ㅎㅎ
https://projecteuler.net/profile/AyoteraLab.png
이렇게 현재 단계를 이미지로 제공도 해주네요... 신기합니당!!
-Ayotera Lab-
댓글