[백준 28282번] 운명 (C++)

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

28282번: 운명

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll left_arr[10001];
ll right_arr[10001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    ll X, K;
    cin >> X >> K;
    for(int i=1; i<=X; i++) //왼쪽 범위
    {
        int n;
        cin >> n;
        left_arr[n]++;
    }

    for(int i=1; i<=X; i++) //오른쪽 범위
    {
        int n;
        cin >> n;
        right_arr[n]++;
    }

    ll result = X*X;
    for(int i=1; i<=K; i++)
    {
        result -= left_arr[i] * right_arr[i]; //전체 경우의 수에서 겹치는 경우 빼기
    }
    cout << result;
    return 0;
}

왼쪽 범위와 오른쪽 범위에 대해 각각 양말의 색깔을 카운팅해준다.

왼쪽 오른쪽 모두 같은 인덱스에 같은 색깔을 저장된다.

 

따라서 반복문으로 탐색을 하면서 인덱스가 같은 경우의 경우의 수를 구해서 전체 가짓수에서 빼주면 된다.

이때 주의해야 할 것은 수의 범위가 커서 몇몇 변수들을 long long으로 선언해줘야 한다.

 

다른 풀이 방법으로는 마찬가지로 인덱스가 같은 경우에 한쪽은 그대로 두고 한쪽은 전체 가짓수 중에서 현재 색깔을 뺀 나머지를 곱해서 더해주는 방식이다.

이 또한 같은 인덱스의 경우 색깔이 중복되므로 중복을 없애주기 위해 한쪽은 현재 색깔을 제외한 나머지 가능한 색깔들을 곱해주는 것이다.

(result += left_arr[i] * (X-right_arr[i]))

 

처음에는 2중 반복문으로 i==j이 같을 때만 넘기고 나머지 경우에 대해 곱해서 더해줬는데 다른 사람 풀이를 보니, 전체 경우의 수에서 중복되는 것만 빼주는 것이 가장 직관적이어서 최종적으로 해당 코드로 다시 제출했다.