문제
해적이 첫 날 1개, 다음 이틀 각 2개, 그 다음 사흘 각 3개, ... 와 같이
k일째 주기에는k개씩k일 동안 금화를 받는다.d일까지의 누적 금화 수를 출력한다.d=0이면 종료.
풀이
k번째 주기는 k일 동안 진행되며 하루에 k개, 합 k²개를 준다. d에서 k를 계속 빼가며 완전한 주기는 k²씩 누적하고, 마지막에 남은 일수가 k보다 작으면 남은 일수 * k를 더한다.
코드
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int d;
while (true) {
cin >> d;
if (d == 0) break;
int r = d;
int tmp = 1;
int sum = 0;
while (r > 0) {
if (r >= tmp) {
sum += tmp * tmp;
r -= tmp;
}
else {
sum += r * tmp;
break;
}
++tmp;
}
cout << d << " " << sum << '\n';
}
return 0;
}복잡도
- 시간: O(√d) (주기 수)
- 공간: O(1)