기록을

문제 링크는 다음과 같다.

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

위와 같은 예시를 보면, 쉽게 이차원 배열을 사용해야겠다는 생각을 떠올릴 수 있다.

특정 학년의 특정 성별을 가지는 학생의 수를 그대로 배열에 저장해준다.

k보다 인원이 작으면 방은 1개만 있으면 되고, 그 이상일 경우 k로 나눈 몫 + 1개만큼 방이 필요하다.

#include<iostream>
using namespace std;

int arr[2][7];

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

	int n, k;
	cin >> n >> k;

	int s, y;
	while (n--) { //n명의 정보를 2차원 배열에 저장
		cin >> s >> y;
		arr[s][y]++;
	}

	int room = 0;

	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= 6; j++) {
			if (!arr[i][j]) //특정 학년과 성별의 학생수가 0이면 continue
				continue;
			
			if (arr[i][j] < k) // k보다 작으므로 방은 하나만 있으면 됨
				room++;
			else { //k보다 크거나 같을 때
				if (arr[i][j] % k == 0) {
					//k로 나눠 떨어질 때
					room = room + arr[i][j] / k;
				}
				else {
					room = room + arr[i][j] / k + 1;
				}
			}
		}
	}

	cout << room << '\n';

	return 0;
}

문제링크

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

순서를 섞었을 때 문자열이 같아질 수 있느냐를 물어보는 문제였다.

단순히 문자열에서, 각 알파벳의 개수를 파악해주고 비교해주면 된다.

#include<iostream>
#include<string>
#include<math.h>
using namespace std;

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

	string org, cpr;
	int orga[26] = { 0, }, cpra[26] = { 0, };

	cin >> org >> cpr;

	for (int i = 0; i < org.length(); i++) {
		orga[org[i] - 'a']++;
	}
	for (int i = 0; i < cpr.length(); i++) {
		cpra[cpr[i] - 'a']++;
	}

	int cnt = 0;
	
	for (int i = 0; i < 26; i++) {
		cnt = cnt + abs(orga[i] - cpra[i]);
	}
	cout << cnt << '\n';

	return 0;
}
/*
strfry와 같은 원리. 단어에 쓰인 알파벳별 개수를 파악해서 비교.
입력 문자열의 길이가 다른 경우도 생각해줘야함
*/

문제링크

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

설명은 코드의 주석으로 대체하겠다.

#include<iostream>
#include<string>
using namespace std;
int A, B, C, arr[10];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> A >> B >> C;
	long long res = A * B*C;	
	string str = to_string(res);
	for (int i = 0; i < str.length(); i++) {
		arr[str[i] - '0']++;
	}
	for (int i = 0; i < 10; i++) {
		cout << arr[i] << '\n';
	}
	return 0;
}
/*
각 자리수의 숫자를 확인하기 위해 계산 결과를 long long에서 string 으로 변환
string으로 변환된 값의 각 자리수인 char에서 int로 변환을 -'0'을 활용
*/

문제 링크

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

섬의 개수를 파악한다고 자주 기술했었는데, 간단하게 floodfill을 수행해주면 된다.

그림의 수를 파악하고, 그림의 넓이를 담아둘 때는 방문 처리 배열을 사용한다.

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

int map[500][500], dist[500][500];
int row, col;

queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0, };

int cnt = 0;
void bfs(pair<int, int> start) {
	cnt++; //섬개수 확인
	q.push(start);
	dist[start.first][start.second]++; 
	int di = 2; //위에서 시작점 방문하면 거리 1이니까, 다음으로 들어갈 거리는 2

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];

			if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 0 || dist[nr][nc] > 0)continue;

			q.push({ nr, nc });
			dist[nr][nc] = di;
			di++;
			
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> row >> col;
	for(int i = 0 ; i < row ; i++)
		for (int j = 0; j < col; j++) {
			cin >> map[i][j];
		}

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			if (map[i][j] == 1 && dist[i][j] == 0)
				bfs({ i, j });
		}
	//방문처리 배열에 카운트를 해뒀기때문에 그 안에서 최댓값을 구하면 된다.
	int Max = -1;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (dist[i][j] > Max)
				Max = dist[i][j];
		}
	}
	cout << cnt << '\n' << Max << '\n';
	return 0;
}

문제링크

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

섬의 개수를 확인하는 방식으로 전형적인 bfs를 사용해서 풀이가 가능하다.

bfs 함수가 실행되는 횟수를 확인하면 된다.

방문하지 않았으면서 배추가 있는 곳이 bfs의 시작점이 된다.

범위 밖을 나가는 요소와 이미 방문한 지점, 방문할 필요가 없는 지점을 제외하면 되는 간단한 bfs이다.

#include<iostream>
#include<queue>
using namespace std;
int map[51][51], vis[51][51];
int m, n, k;

int cnt = 0;
queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
void bfs(pair<int, int> start) { //전형적인 bfs
	cnt++; //섬 개수 추가
	q.push(start);
	vis[start.first][start.second] = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			//범위 나가거나 배추가 없는 곳이거나 이미 방문한 곳이면 continue
			if (nr < 0 || nc < 0 || nr >= n || nc >= m || vis[nr][nc] == 1 || map[nr][nc] == 0)continue;
			
			q.push({ nr, nc });
			vis[nr][nc] = 1;

		}
	}

}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	while (tc--) {

		cin >> m >> n >> k;

		int n1, n2;
		while (k--) {
			cin >> n1 >> n2;
			map[n2][n1] = 1;
		}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (map[i][j] == 1 && vis[i][j] == 0)
					bfs({ i, j }); //1인 지점 넘겨줘야함

		cout << cnt << '\n';

		//이후로 초기화
		for (int i = 0; i < n; i++) 
			for (int j = 0; j < m; j++) {
				map[i][j] = 0;
				vis[i][j] = 0;
			}
		cnt = 0;
	}

	return 0;
}