문제 개요
첫날인 월요일에 은행에 1루피(Rs)를 입금했다고 가정해 보겠습니다. 그다음 날인 화요일부터 일요일까지는 매일 전날보다 1루피씩 더 많이 입금하고, 이후 매주 월요일에는 지난주 월요일보다 1루피씩 더 많이 입금하는 규칙입니다. 이때 정수 n이 주어지면, n일째 되는 날까지 은행에 총 얼마가 쌓이는지 구하는 것이 이 문제의 목표입니다.
예시로 이해하기
예를 들어 입력값이 n = 17이라면 출력은 75가 됩니다.
첫째 주에는 월요일 1루피, 화요일 2루피처럼 하루씩 늘려 일요일에 7루피까지 넣습니다. 둘째 주 월요일에는 2루피, 화요일에는 3루피를 넣어 일요일에는 8루피가 됩니다. 셋째 주 월요일에는 3루피, 화요일에는 4루피, 마지막 날인 수요일에는 5루피를 넣습니다.
따라서 총합은 다음과 같습니다.
(1+2+3+4+5+6+7) + (2+3+4+5+6+7+8) + (3+4+5) = 75루피
해결 접근 방법
한 주(월요일~일요일)의 입금액 합계는 1+2+3+4+5+6+7 = 28입니다. 이 첫째 주 합계(s = 28)를 기준으로 삼으면, 매주 시작 금액이 1루피씩 커진다는 규칙을 이용해 효율적으로 계산할 수 있습니다.
s := 28로 초기화 (첫째 주 합계)
res := 0으로 초기화
만약 n > 7이라면:
res := s
div := n을 7로 나눈 몫
i를 1부터 div-1까지 반복하며: res := res + s + 7×i
rem := n을 7로 나눈 나머지
i를 1부터 rem까지 반복하며: res := res + i + div
그렇지 않은 경우(n ≤ 7):
i를 1부터 n까지 반복하며: res := res + i
res 반환
파이썬 구현 예제
아래 구현을 통해 동작 방식을 더 자세히 이해해 보겠습니다.
def solve(n): s = 28 res = 0 if n>7: res = s div = n//7 for i in range(1,div): res += s+7*i rem = n % 7 for i in range(1,rem+1): res += i+div else: for i in range(1,n+1): res+=i return res n = 17 print(solve(n))
입력
17
출력
75
정리
이 알고리즘은 전체 기간을 '완전한 주'와 '남은 일수'로 나누어 처리합니다. 완전한 주의 합계는 등차수열의 성질을 이용해 한 번의 곱셈으로 계산하고, 남은 일수만 반복문으로 더하므로 시간 복잡도는 O(n)으로 효율적입니다. 이러한 패턴 인식 기반 접근은 비슷한 유형의 누적 합계 문제에서도 유용하게 활용될 수 있습니다.