마트료시카 합치기 (feat. 백준, 25631번)

마트료시카 합치기
https://www.acmicpc.net/problem/25631

25631번: 마트료시카 합치기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, ans = 0, arr[1000];
    bool visit[1000]{false};
    cin >> N;
    for(register int n = 0; n < N; ++n)
        cin >> arr[n];
    sort(arr, arr + N);
    for(register int i = 0, j; i < N - 1; ++i)
        for(register int j = i + 1; j < N; ++j)
            if(arr[i] < arr[j] && !visit[j]){
                visit[j] = true, arr[i] = 0;
                break;
            }
    for(register int n = 0; n < N; ++n)
        if(arr[n] != 0)
            ++ans;
    cout << ans;
    return 0;
}
// *&)*@*

 

i와 j간 순서 조건은 없으므로 정렬된 상태에서 선택 정렬처럼 1번째와 N번째간 마트료시카 크기를 비교합니다.

또한 비어있는 N번째인 경우에만 이동이 가능하므로, 방문 체킹을 하며 방문되지 않은 곳만 수행합니다.

1번째는 N번째로 이동되므로 0을 대입하여 초기화시켜 줍니다.