[BOJ] 18868, 18869 :: 멀티버스Ⅰ, 멀티버스Ⅱ

문제 소개

2020.04.11 기준,  solved.ac 브론즈 1티어, 실버 1티어 문제입니다.

 

바로 이전 글인 좌표 압축을 이용하는 문제입니다.

2020/04/11 - [Problem Solving/BOJ] - [BOJ] 18870: 좌표 압축

 

문제 링크

https://www.acmicpc.net/problem/18868

18868번: 멀티버스 Ⅰ

https://www.acmicpc.net/problem/18869

18869번: 멀티버스 Ⅱ

 

아이디어

일단, 위에 언급했듯이 좌표 압축 글을 먼저 읽어주세요.

 

제 풀이는 조금 무식하게 접근하는 풀이입니다.

1) 좌표 압축으로 주어지는 행성의 크기들을 원하는 숫자들로 바꾼다.

2) 바뀐 숫자들이 최대 10000 안에 들어올 것이므로 5자리의 문자열로 치환하고 모두 합쳐준다.

3) 합친 문자열들을 모아놓고, 정렬한 뒤 같은 것들의 개수를 세어준다. (이때 같은 것들의 개수를 세는 과정을 O(n^2) 과정으로 처리하면 안됩니다.)

4) 같은 것들의 개수가 a라면, a*(a-1)/2(aC2, 조합계산) 으로 누적한다. 

코드(cpp)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int M,N;
int ar[11000];
int b[11000];
vector <string> V;
int main() {
    cin >> M >> N;
    for(int t=0; t < M; t++) {
        map <int, int> m;
        string current = "";
        int cnt = 0;
        for(int x=0; x < N; x++) {
            cin >> ar[x];
            b[x] = ar[x];
        }
        sort(b,b+N);
        m[b[0]] = cnt++;
        for(int x=1; x<N; x++) {
            if(b[x] != b[x-1]) m[b[x]] = cnt++;
        }
        for(int x=0; x<N; x++) {
            int k = m[ar[x]];
            int digit = 0;
            while(k > 0) {
                digit++;
                k/=10;
            }
            for(int y =0; y< 5-digit; y++) {
                current += "0";
            }
            k = m[ar[x]];
            while(k>0) {
                current += (char) (k%10 + 48);
                k/=10;
            }
        }
        V.push_back(current);
    }
    sort(V.begin(),V.end());

    int same_cnt = 1;
    int ans = 0;

    for(int x=1; x<V.size(); x++) {
        if(V[x] != V[x-1]) {
            ans += same_cnt * (same_cnt-1) / 2;
            same_cnt = 1;
        }
        else {
            same_cnt++;
        }
    }
    ans += same_cnt * (same_cnt - 1) / 2;

    cout<<ans;
}

 

Rmx