N

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

SW Expert Academy

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

naeunchan 2020. 11. 10. 13:44
728x90
반응형

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

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

우선 배의 주기를 체크하는 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;
}
        
728x90
반응형