굳건하게

문제 : https://www.acmicpc.net/problem/11866

[알고리즘풀이]

자료구조 queue를 이용해서 k번 째마다 제거(pop)를 진행하고, 1 ~ k-1번 원소는 다시 뒤로 삽입(push)을 진행한다.

queue(큐) 설명 : https://travelbeeee.tistory.com/7?category=807507

#include<iostream>
#include<queue>
#include<string>

using namespace std;

int main(void) {
	int n, m;
	queue<int> q;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		q.push(i);
	cout << "<";
	while (!q.empty()) {
		for (int i = 0; i < m - 1; i++) {
			int temp = q.front();
			q.pop();
			q.push(temp);
		}
		if (q.size() == 1)
			cout << q.front() << '>';
		else
			cout << q.front() << ", ";
		q.pop();
	}
}

문제 : https://www.acmicpc.net/problem/2164

[알고리즘풀이]

제일 위에 있는 카드는 버릴 수 있고(pop), 카드는 오로지 제일 아래로만 추가하므로(push) 전형적인 FIFO 이다.

즉, 자료구조 queue(큐)를 이용하면 쉽게 해결할 수 있는 문제다.

queue(큐) 설명 : https://travelbeeee.tistory.com/7?category=807507

#include<iostream>
#include<queue>
#include<string>

using namespace std;

int main(void) {
	int n;
	queue<int> q;
	cin >> n;
	for (int i = 1; i <= n; i++)
		q.push(i);
	while (q.size() != 1) {
		q.pop();
		int y = q.front();
		q.pop();
		q.push(y);
	}
	cout << q.front();
}

문제 : https://www.acmicpc.net/problem/10845

[알고리즘풀이]

자료구조 queue를 이용해서 문제에서 원하는대로 명령이 들어오면 명령을 실행하면 된다.

#include<iostream>
#include<queue>
#include<string>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int n;
	queue<int> q;
	cin >> n;
	while (n--) {
		string input;
		cin >> input;
		if (input == "push") {
			int input2;
			cin >> input2;
			q.push(input2);
		}
		else if (input == "front") {
			if (q.empty())
				cout << "-1\n";
			else
				cout << q.front() << '\n';
		}
		else if (input == "pop") {
			if (q.empty())
				cout << "-1\n";
			else {
				cout << q.front() << '\n';
				q.pop();
			}
		}
		else if (input == "size") {
			cout << q.size() << '\n';
		}
		else if (input == "empty") {
			if (q.empty())
				cout << "1\n";
			else
				cout << "0\n";
		}
		else if (input == "front"){
			if (q.empty())
				cout << "-1\n";
			else
				cout << q.front() << '\n';
		}
		else {
			if (q.empty())
				cout << "-1\n";
			else
				cout << q.back() << '\n';
		}
	}
}

문제 : https://www.acmicpc.net/problem/17436

[알고리즘풀이]

N개의 소수를 p1, p2, ⋯ pn 이라고 하자.

그리고 1 ~ M 이하의 자연수 중에서 p1으로 나눠지는 수들의 집합을 P1, ⋯ pn으로 나눠지는 수들의 집합을 Pn 이라고 한다면, 우리가 구하고 싶은 답은 n(P1 U P2 U ⋯ U Pn)이 될 것이다. ( 합집합의 원소의 개수 )

n(P1 U P2 U ⋯ U Pn)

=+n(P1) + n(P2) + ⋯ + n(Pn)

  -n(P1 ∩ P2) -n(P1 ∩ P3) - ⋯ - n(Pn-1 ∩ Pn)

  +n(P1 ∩ P2 ∩ P3) + ⋯ + n(Pn-2 ∩ Pn-1 ∩ Pn)

  - ⋯

  (-1)^(n-1) * n(P1 ∩ P2 ∩ ⋯ ∩Pn)

이고 모두 소수이므로 서로소 성질에 의해 n(Pi ∩ Pj) = M / (Pi * Pj) 가 성립한다.

따라서, 백트레킹 기법을 활용해 위의 공식을 계산해주면 된다.

#include<iostream>
#include<vector>

using namespace std;

long long answer, m;
int n, p[10];

void bt(int, int, int, vector<int>);

int main(void){
	cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++){
        // i 개씩 뽑을거야. 안겹치게 오름차순으로
        for(int j = 1; j <= n; j++){
            vector<int> v;
            v.push_back(j);
            bt(1, j, i, v);
            v.pop_back();
        }
    }
    cout << answer;
}

void bt(int size, int start, int l, vector<int> v){
    if(size == l){
    	if(l % 2 == 1){
            long long temp = 1;
            for(int i = 0; i < l ; i++){
                temp *= p[v[i] - 1];
            }
            answer += m / temp;
        }
        else{
            long long temp = 1;
            for(int i =0; i < l; i++)
                temp *= p[v[i] - 1];
            answer -= m / temp;
        }
        return;
    }
    for(int i = start + 1; i <= n; i++){
        v.push_back(i);
        bt(size + 1,i,l,v);
        v.pop_back();
    }
}