[C++] 백준 BOJ 1834 나머지와 몫이 같은 수

문제 링크 : https://boj.kr/1834

이 문제는 막상 해보니 어렵지 않았다.

종이에 직접 써보면서 규칙을 찾으니 쉽게 점화식을 찾을 수 있었다.

[N = 젯수 일 때, 피젯수(몫,나머지) 순서]

N = 1 일 때, 존재하지 않음

N = 2 일 때, 3(1,1)

N = 3 일 때, 4(1,1) 8(2,2)

N = 4 일 때, 5(1,1) 10(2,2) 15(3,3)

N = 5 일 때, 6(1,1) 12(2,2) 18(3,3) 24(4,4)

벌써부터 규칙이 보인다.

1. 몫과 나머지가 같은 수들은 N+1의 배수들

2. 배수의 갯수는 N-1개

점화식을 구해보면 (N + 1) * i 가 된다. 

단, 이 문제는 입력 최대 값이 2,000,000이기 때문에 최대로 올 수 있는 값은 sigma(i=1~1,999,999) 2,000,001 * i 이기 때문에 int의 표현 범위로는 나타낼 수 없다. long long을 사용하도록 해야한다.

// BOJ 1834 나머지와 몫이 같은 수
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    long long num;
    long long result = 0;
    cin >> num;
    // num+1의 배수를 num-1회 누적
    for (long long i = 1; i < num; i++)
        result += (num + 1) * i;
 
    cout << result;
 
    return 0;
}