Hoeun Wang - Blog

https://www.acmicpc.net/problem/1927

문제해석

이 문제는 큐에 수를 추가하고 가장 작은 값부터 출력해주는 문제이다.

선입선출의 특징을 가진 큐를 생각해서 어떻게 문제를 해결해 나가야 할지 고민해봐야한다.

코드

#include<iostream>
#include<queue>
using namespace std;

int N;

priority_queue<int, vector<int>, greater<int>> pq;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;

		if (a == 0) {
			if (pq.empty()) {
				cout << 0 << "\n";
			}
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
		}
		else {
			pq.push(a);
		}
	}

	return 0;

}

문제풀이

이 문제는 물론 다른 방법이 존재하지만, c++로 문제를 푸는 사람들은 우선순위 큐 STL을 사용하면 좋은 문제이다.

우선순위 큐인 priority_queue는 일반적인 queue와는 다르게 선입 선출 형태가 아닌 지정된 값을 통해 queue 내부의 우선순위를 정리 할 수 있다. 

우선순위 큐는

priority_queue<자료형, 구현체, 비교연산자> pq;

다음과 같이 정의 된다.

나는 자료형엔 int 구현체에는 queue를 사용해주었는데 비교연산자에서 greater<int>를 작성해주었다. greater<자료형>은 기본 비교연산자이며 가장 작은 값부터 나열을 시켜준다.(큰값부터 나열은 less<자료형> 활용해주기.)

이 STL을 사용하여 코드를 작성하면 아주 간단하게 문제를 해결할 수있다. STL을 잘 이해하고 활용하는 방법도 많이 시도해보도록 하자.

https://www.acmicpc.net/problem/2343

문제해석

비디오의 개수와 블루레이의 개수를 입력 받은 후 비디오의 길이를 각각 입력받고, 블루레이에 비디오를 분배 하였을 때, 블루레이의 최솟값을 구하는 문제이다.

코드

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
int N, M;
int a[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int max, min = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		max += a[i];	
	}
	min = *max_element(a, a + N);	

	while (min <= max) {	
		int mid = (min + max) / 2;	

		int sum = 0, count = 0;	
		for (int i = 0; i < N; i++) {
			if (sum + a[i] > mid) {
				sum = 0;
				count++;
			}
			sum += a[i];
		}
		if (sum != 0) count++;	
		
        	
		if (count > M) {
			min = mid + 1;
		}
		else {
			max = mid - 1;
		}
	}
    
	cout << min;
	return 0;
}

문제풀이

먼저 입력 수의 범위를 살펴보았을 때 100000 이하로 나타나져 있기 때문에 이분탐색으로 풀어야 한다는 것을 미리 깨달아야 한다.

그렇게 판단 후 문제를 풀어보면, 비디오 개수 (N) 블루레이 개수 (M) 각각의 비디오 길이 배열a 를 입력 받고 가장 최대크기의 블루레이 크기가 될 수 있는 모든 비디오들의 길이를 합한 값을 max라는 변수에 저장해주고, 가장 작은 블루레이 크기가 될 수 있는 비디오 길이중 가장 긴 값을 min에 넣어준다.

그런 후, max값이 min값보다 같거나 클때 동안 다음 과정을 반복해주면 되는데, 임의로 우리가 지정한 mid라는 블루레이의 크기 값에 비디오들을 하나씩 넣어보며 만약 값이 더 크게 되면 필요한 블루레이 갯수를 한개 증가시켜준다. 그렇게 계속해서 비디오를 넣어보며 합을 구해주고 그 합을 활용해 큰지 적은지 판단하여 둔다. 모든 비디오를 다 넣어준 후에 count 한 블루에이 개수가 M보다 크면 기존 블루레이 개수를 늘려주고 적으면 줄여준다.

그렇게 한 후 최종 답이 들어있는 변수인 min을 출력해주면 해결할 수 있는 문제이다.

https://www.acmicpc.net/problem/6603

문제해석

k개 만큼에 수를 뽑은 후, 그 수들을 가지고 나올 수 있는 모든 경우의 수에서의 6자리 숫자 집합을 생성하여 출력해주는 문제이다.

코드

#include <iostream>
#include <vector>
using namespace std;

int S[13];
int L[6];
int k;
void solved(int s, int l) {
	if (l == 6) {
		for (int i = 0; i < 6; i++) {
			cout << L[i] << " ";
		}
		cout << endl;
		return;
	}
	
	for (int i = s; i < k; i++) {
		L[l] = S[i];
		solved(i+1, l+1);
	}
}
int main(void) {
	while (1) {
		cin >> k;
		if (k == 0) break;
		for (int i = 0; i < k; i++) {
			cin >> S[i];
		}
		solved(0, 0);
		cout << endl;
	}
}

문제풀이