백준 1834번 [나머지와 몫이 같은 수](C++) -yes6686- 티스토리

백준 문제 풀이: 1834 (나머지와 몫이 같은 수)

---

문제 링크: https://www.acmicpc.net/problem/1834

문제 설명:

정수 **N**이 주어질 때, 나머지와 몫이 같은 모든 자연수 **x**를 찾고, 그 합을 구해야 합니다. 주어진 조건:

• 나머지와 몫이 같다는 것은 \( x \div N \)의 몫과 \( x \% N \)의 나머지가 같다는 의미입니다.
• 모든 \( x \)를 만족하는 \( x \)의 합을 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long int ans = 0; // 결과 값을 저장할 변수
    int n; // 입력된 N
    cin >> n;

    // 나머지와 몫이 같은 수를 계산
    for (long long int i = 1; i < n; i++) {
        ans += (i * n) + i; // x = i * N + i
    }

    cout << ans; // 결과 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 문제 분석: \( x \div N \)에서 몫과 나머지가 같기 위해 \( x \)는 \( i \cdot N + i \) 형태가 되어야 합니다. 여기서 \( i \)는 **1부터 N-1**까지의 수입니다.
• 반복문: - \( i \)를 **1부터 N-1**까지 반복하면서 \( x = i \cdot N + i \)를 계산합니다. - 결과를 누적합으로 더해줍니다.
• 출력: - 최종적으로 합산된 결과를 출력합니다.

시간 복잡도 분석

• 반복문은 \( i = 1 \)부터 \( i = N-1 \)까지 수행되므로, 시간 복잡도는 **O(N)**입니다.
• 입력 범위가 \( N \leq 10^6 \)이므로 충분히 빠르게 수행됩니다.

---

결과

나머지와 몫이 같은 수들의 합을 출력합니다.

• 입력 예시:

  4

• 출력 예시:

  40

추가 설명:

• \( x \)는 \( i \cdot N + i \)이므로, **공식화**된 형태를 반복 계산하는 방법이 효율적입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!