Problem D 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1520/problem/D

aj - ai = j - i 조건을 aj - j = ai - i로 바꿔 생각할 수 있다.

배열 a의 각 원소의 ai - i 값을 구하고 해당 값의 개수를 구하기 위해 map에 저장한다.

map에서 ai - i의 key 값에 해당하는 값을 올려주기 때문에 같은 원소의 개수를 알 수 있다.

원소의 개수가 x 개일 때, 원소의 쌍은 i < j 이어야 하기 때문에

쌍의 개수는 x(x - 1) / 2 개가 된다.

모든 값의 쌍의 개수를 구하여 더하면 답이 된다.

여기서 쌍의 개수를 구하는 과정을 이용해서 더 간단하게 알고리즘을 바꿔보면

원소의 개수가 x 개일 때 쌍의 개수는 1 + 2 + 3 + ~~ + (x - 2) + (x - 1) 이다.

그렇기 때문에 map에 저장한 후 계산하지 않고 각 원소를 입력받을 때마다 map의 ai - i의 개수를 더해주기 전에 기존의 ai - i의 개수를 더해주면 더 간단하게 바꿀 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <map>
 
using namespace std;
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
 
        int n;
        cin >> n;
 
        map<int, int> m;
        long long ans = 0;
 
        for (int i = 1; i <= n; i++) {
            int a;
            cin >> a;
            ans += m[a - i];
            m[a - i]++;
        }
 
        cout << ans << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기