(SWEA c++)4371. 항구에 들어오는 배

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWMedCxalW8DFAXd&categoryId=AWMedCxalW8DFAXd&categoryType=CODE

SW Expert Academy

우선 배의 주기를 체크하는 bool형 벡터 check를 전역변수로 선언한다.

그리고 최소 수의 배를 확인하기 위해 num과 max, up 변수, v 벡터를 이용하였다.

 

먼저 num은 N개의 배 중에서 1일날 확인한 배를 뺀 결과이다.

즉, 체크해야 하는 날의 수를 확인하는 변수.

 

max는 마지막 날을 확인하는 변수로, for문을 크게 돌지 않기 위해 사용하였다.

up 변수는 bool형으로 true가 되면 배의 수를 +1 시켜주는 역할을 한다.

v벡터는 각 날짜에서 1을 뺀 값으로 등차수열을 찾기 위한 값이다.

 

먼저 check 벡터에 들어온 날을 true로 바꿔준다.

모든 날을 입력받고, max는 v.back() + 1을 해주어 마지막 날을 저장하도록 한다.

 

v 벡터의 0번째 인자가 아닌 1번째 인자부터 for문을 돌도록 한다.

up 변수를 false로 초기화 해주고 다음 for문으로 진입.

두번째 for문에서는 v[i]번째 값을 더하면서 정해진 규칙에 따라 정착하는 배를 false로 바꿔주도록 한다.(up은 true로 변환)

그러면서 num--를 해주도록 한다.

 

up이 true라면 1개의 배가 모든 날짜를 돌았으므로 ans++을 해주도록 한다.

#include <iostream>
#include <vector>

using namespace std;
vector<bool> check(1000000001, false);

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        int N, num, ans = 0, max;
        vector<int> v;
        
        cin >> N;
        num = N - 1;
        
        for(int i = 0; i < N; i++)
        {
            int tmp;
            cin >> tmp;
            check[tmp] = true;
            v.push_back(tmp - 1);
        }
        max = v.back() + 1;
        
        for(int i = 1; i < v.size(); i++)
        {
            bool up = false;
            for(int j = 1 + v[i]; j <= max; j += v[i])
            {
                if(check[j])
                {
                    check[j] = false;
                    num--;
                    up = true;
                }
            }
            if(up)
            	ans++;
            if(num < 1)
                break;
        }
        
        cout << "#" << tc << " " << ans << endl;
    }
    return 0;
}