[백준 2853번] 배 (C++)

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

2853번: 배

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

int arr[5001]; //배의 방문 일자
int check[5001]; //배의 방문 체크
map<int, int>m; 

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

    int N, cnt = 0;
    cin >> N;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
        m[arr[i]] = i;
    }

    for(int i=1; i<N; i++)
    {
        if(check[i]) continue; //이미 방문했다면 패스
        cnt++; //배의 수 증가
        int diff = arr[i] - arr[0]; //간격

        for(int j=arr[i]; j<=arr[N-1]; j+=diff) //해당 간격의 배 체크
        {
            int idx = m[j];
            check[idx]=1; //방문체크
        }
    }

    cout << cnt;
    return 0;
}

먼저 첫번째 값과 두번째값의 간격을 구하고 해당 간격만큼의 값들을 방문처리하여 지우는 식으로 풀었다.

기존에 check[arr[i]] 이런식으로 해당 값의 위치로 방문처리를 했는데 문제의 값의 범위를 보면 10억까지 있기에 배열의 범위가 10억이어야 위에 방식으로 가능하여 map으로 바꿔서 풀었다.

 

map에 해당 값들과 인덱스를 저장하고, 해당 값의 인덱스를 이용하여 방문 처리를 해주었다.

반복문의 맨 위에는 이미 방문했으면 넘기도록 하여 방문하지 않은 값들에 대해서만 해당 값의 간격 만큼 또 확인하도록 하였다.