congcoding

1. 문제 링크

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

2. 문제 설명

N명의 사람이 원형으로 앉아있을 때 순서대로 K번째 사람을 제거하는 순서를 출력하는 문제입니다.

3. 소스코드

BOJ 1158번 요세푸스 문제 C++ 풀이입니다.

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, K, idx;
	cin >> N >> K;
	vector<int> v(N);
	idx = K - 1;

	for (int i = 0; i < N; i++) v[i] = i + 1;
	cout << '<';
	while (v.size() != 1) {
		cout << v[idx] << ", ";
		v.erase(v.begin() + idx);
		idx = (idx + K - 1) % v.size();
	}
	cout << v[0] << '>';

	return 0;
}

먼저 vector와 인덱스를 이용한 풀이입니다.

인덱스는 0부터 시작하므로 13번 라인에서 idx를 K - 1로 초기화했습니다.

마지막 요소를 출력할 때는 ", "를 출력하지 않으므로 while문의 조건을 v.size() != 1로 설정했습니다.

먼저 idx에 있는 요소를 출력한 후, erase합니다.

idx를 K - 1만큼 증가시켰을 때, v의 범위를 초과하는 경우가 있으므로 size로 나눴을 때의 나머지를 대입합니다.

마지막으로 남은 요소를 출력하고 '>'를 같이 출력합니다.

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, K, idx;
	cin >> N >> K;
	vector<int> v(N);
	vector<int>::iterator t = v.begin();
	for (int i = 0; i < N; i++) v[i] = i + 1;

	cout << '<';
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < K - 1; j++)
			if (++t == v.end()) t = v.begin();
		cout << *t << ", ";
		t = v.erase(t);
		if (t == v.end()) t = v.begin();
	}
	cout << v[0] << '>';

	return 0;
}

vector와 iterator를 이용한 풀이입니다.

마지막 요소를 출력할 때는 ", "를 출력하지 않으므로 바깥쪽 for문을 N - 1전까지만 돌게 설정했습니다.

vector와 index를 이용한 풀이처럼 while문의 조건을 v.size != 1로 설정해도 됩니다.

안쪽 for문은 K - 1번 돌면서 t를 한칸씩 이동시켜줍니다.

이 때 t가 end에 도달하면 v.begin()을 대입해줍니다. 원형이라고 생각하면 이해하기 쉽습니다.

현재 t위치의 요소를 출력한 후, 삭제(v.erase(t))를 해줍니다.

erase함수는 삭제한 요소의 다음 요소를 return하므로 이를 다시 t에 대입했습니다.

이 때 t가 end에 도달했을 경우 v.begin()을 대입해줍니다.

이 과정을 생략하면 안쪽 for문을 돌 때 ++t하는 과정에서 segmentation fault가 발생하므로 주의해야 합니다.

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, K, idx;
	cin >> N >> K;
	list<int> l;

	for (int i = 0; i < N; i++) l.push_back(i + 1);
	cout << '<';
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < K - 1; j++) {
			l.push_back(l.front());
			l.pop_front();
		}
		cout << l.front() << ", ";
		l.pop_front();
	}
	cout << l.front() << '>';

	return 0;
}

list 이용한 풀이입니다.

마지막 요소를 출력할 때는 ", "를 출력하지 않으므로 바깥쪽 for문을 N - 1전까지만 돌게 설정했습니다.

vector와 인덱스를 이용한 풀이처럼 while문의 조건을 l.size != 1로 설정해도 됩니다.

안쪽 for문은 K - 1번씩 돌면서 list의 맨 앞에 있는 요소를 맨 뒤로 옮겨줬습니다.

이를 구현하려면 맨 앞에 있는 요소(l.front())를 맨 뒤에 넣고(l.push_back), 맨 앞의 요소를 삭제(l.pop_front())하면 됩니다.

뒤로 다 옮긴 후 맨 앞에 있는 요소(l.front())를 출력한 후, 맨 앞의 요소를 삭제(l.pop_front())하면 됩니다.

1. 문제 링크

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

2. 문제 설명

숫자를 입력받은 후 이를 표현하기 위해 0부터 9까지 숫자가 하나씩 들어있는 세트의 최소 필요 개수를 출력하는 문제입니다.

3. 소스코드

BOJ 1475번 방 번호 C++ 풀이입니다.

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N;
	vector<int> v(9);
	cin >> N;

	if (N == 0) v[0]++;
	while (N > 0) {
		if (N % 10 == 9) v[6]++;
		else v[N % 10]++;
		N /= 10;
	}
	v[6] = ceil((double)v[6] / 2);
	cout << *max_element(v.begin(), v.end());

	return 0;
}

6은 9를 뒤집어서 이용할 수 있기 때문에 9를 입력받으면 6의 자리에 +1을 해줬습니다.

한 세트에 6과 9가 들어있으므로 v[6]은 /2를 해준 후 ceil함수를 이용해 올림했습니다.

마지막으로 max_element함수를 이용해 최댓값을 출력해주면 됩니다.

1. 문제 링크

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

2. 문제 설명

수학여행에 참가하는 학생의 정보를 입력받아, 학년과 성별로 방을 배정할 때 필요한 최소한의 방의 수를 출력하는 문제입니다.

3. 소스코드

BOJ 13300번 방 배정 C++ 풀이입니다.

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, K, r, c, result = 0;
	int arr[2][6] = {};
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> r >> c;
		arr[r][c - 1]++;
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 6; j++) {
			result += ceil((double)arr[i][j] / K);
		}
	}
	cout << result;

	return 0;
}

학생의 정보를 성별과 학년으로 저장하기 위해 11번 라인에서 arr[2][6]을 선언하고 0으로 초기했습니다.

학생의 성별은 0, 1이지만 학년이 1부터 6까지 이므로 arr에 학년 정보를 저장할 때는 -1을 해줬습니다.

arr의 각 요소들을 방에 배정할 수 있는 최대 인원 수로 나누고 ceil함수를 이용해서 올림해줬습니다.

이때 arr[i][j]나 K를 double로 형변환해주지 않으면 int끼리 연산돼서 이미 내림된 결과에

ceil함수를 적용하는 것이기 때문에 올림이 되지 않으니 주의해야 합니다.