Seongkyun Han's blog
191018 백준 알고리즘 문제풀기
18 Oct 2019 | baekjoon[13458] 시험 감독
- 난이도: 하
- 문제의 난이도 자체는 어렵지 않았다.
- 문제의 이해부터 구현까지 40분정도 소요되었다.
- 수의 입출력 부분때문에 많은 시간을 낭비했다.
- 또한 문제의 조건이 명확하지 않아서 시간이 많이 낭비됐다.
- 그리고 while문을 이용해 계속 빼는식으로 매 칸 인원을 줄여나가 시간초과가 떳다.
- 이는 간단하게 나누기를 해서 해결 가능한 문제였지만 당시엔 쉽게 떠오르지 않았다.
- 문제
- https://www.acmicpc.net/problem/13458
- 총 N개의 시험장이 있고, 각 칸에는 응시자 수가 주어진다.
- 각 시험장에는 총감독관 1명, 부감독관 여러명이 있다.
- 총감독관은 1명만 필수로 있어야 하고, 부감독관은 상관없다.
- 다음으로 인원수 B, C가 주어질 때, B는 총감독관 커버 인원수, C는 부감독관 커버 인원수를 의미한다.
- 응시장 상태가 주어질 때 최소 필요 감독관 수를 출력한다.
- 풀이
- 입력을 받는다.
- 매 칸마다 총감독관 인원수를 뺀다.
- 이 때, 빼진 수가 음수가 될 경우 그냥 넘어가야 한다!
- 매 칸 남은 수는 부감독관 인원수로 나눈다.
- 나머지가 존재할 경우, 나눈 수+1을 한다.
- 최솟값을 비교해 저장한다.
- 항상 입출력 수의 크기를 고려해야 할 듯 하다..
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#define MAX 2147483647
using namespace std;
vector<int> A;
int main()
{
int N;
scanf("%d", &N);
int input;
while (N--)
{
scanf("%d", &input);
A.push_back(input);
}
long long B, C;
scanf("%lld %lld", &B, &C);
long long ans = 0;
int length = int(A.size());
for (int i = 0; i < length; i++)
{
A[i] -= B;
ans++;
if (A[i] < 0) continue;
long long div = A[i] / C;
long long rest = A[i] % C;
if (rest != 0) div++;
ans += div;
}
printf("%lld\n", ans);
//std::system("pause");
return 0;
}
[2146] 다리 만들기
- 난이도: 중
- 문제 자체는 크게 어렵지 않았다.
- 문제를 읽자마지 풀이가 바로 떠올랐고, 생각대로 푸니 바로 맞았다.
- 총 푸는데 1시간도 소요되지 않았다.
- BFS를 이용해 섬을 그룹짓고, 다른 섬으로 가야하는 가장자리 정보들을 따로 저장한다음에 브루트포스처럼 모든 경우의 수를 비교해 최솟값을 찾는다.
- 다리를 하나만 놓으면 되서 비교적 쉽게 풀린 듯 하다.
- 문제
- https://www.acmicpc.net/problem/2146
- 크기 N(100이하)의 맵이 주어지고, 0은 바다, 1은 육지를 나타낸다.
- 항상 두 개 이사으이 섬이 있는 데이터만 입력으로 주어질 때, 가장 짧은 다리 하나를 놓을 때의 다리 길이를 구한다.
- 문제를 나누면
- 입력을 받고
- 섬을 그룹짓고
- 섬을 그룹지으면서 가장자리 좌표들을 저장한다음
- 모든 가장자리 좌표들에 대해 다른 섬을 만날때까지 BFS로 탐색한다.
- 다른 섬을 만나면 다리가 완성된것으로 최솟값을 찾는다.
- 풀이
- 입력을 받고
- 섬을 그룹짓는다
- 전체 맵에서 육지를 찾고, 해당 육지는 섬 번호로 check 맵을 모두 초기화한다.
- 이 때, nx와 ny가 육지에서 바다로 변하는 순간의 cx, cy는 다리가 시작될 수 있는 부분으로 edge에 따로 저장한다.
- 현재 섬을 BFS로 모두 탐색했으면 섬 번호를 1 증가시키고 다시 새로운 육지를 탐색한다.
- 전체 맵에서 육지를 찾고, 해당 육지는 섬 번호로 check 맵을 모두 초기화한다.
- 모든 가장자리 좌표에서 다리를 만든다.
- 섬 번호가 다 메겨졌으면, 다시 BFS를 이용해 다리를 만들기 시작한다.
- 만약 다음 좌표인 nx, by 자리가 같은 섬이거나 방문했던적이라면 넘어가고, 다음 섬을 찾았다면 최소 거리를 구한다음 초기화한다.
- 해당 좌표 check 값이 최소 거리가 될 것이다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
#define MAX 2147483647
using namespace std;
struct info
{
int x, y, unum;
};
int map[101][101];
int unions[101][101];
int check[101][101];
int answer = MAX;
vector<info> edges;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int main()
{
int N;
scanf("%d", &N);
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
scanf("%d", &map[j][i]);
}
}
int edges_idx = 0;
edges.push_back({ -1,-1,-1 });
//섬 그룹짓기
int cnt_union = 1;
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
if (map[j][i] == 0) continue; // 현재자리 바다라면 넘어가고
if (unions[j][i] != 0) continue; // 현재자리 번호가 메겨졌다면 넘어간다.
queue<pair<int, int>> q;
unions[j][i] = cnt_union; // 위 조건을 모두 통과했으면 현재자리부터 탐색 시작.
q.push(make_pair(i, j));
while (!q.empty())
{
int cx = q.front().first;
int cy = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int nx = cx + dx[k];
int ny = cy + dy[k];
if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue;
if (map[ny][nx] == 0 && map[cy][cx] == 1)
{//가장자리 부분이라면
if (edges[edges_idx].x != cx || edges[edges_idx].y != cy)
{//현재좌표와 이전좌표 다르다면 가장자리 좌표와 팀 뽑기
// 이는 현재좌표 cx, cy 기준으로 nx, ny를 찾기때문에 cx,cy의 중복을 방지하기 위함이다.
// edges_idx는 바로 전 인덱스를 가리킨다.
edges.push_back({ cx,cy,cnt_union });
edges_idx++;
}
}
else
{//가장자리 부분이 아니라면
if (unions[ny][nx] != 0) continue;
unions[ny][nx] = cnt_union;
q.push(make_pair(nx, ny));
}
}
}
cnt_union++;
}
}
// 다른 섬 찾아가기
for (int i = 1; i<int(edges.size()); i++)
{
memset(&check, 0, sizeof(check));
queue<tuple<int, int, int>> q;
int cx = edges[i].x;
int cy = edges[i].y;
int cu = edges[i].unum;
check[cy][cx] = 1;
q.push(make_tuple(cx, cy, cu));
while (!q.empty())
{
tie(cx, cy, cu) = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int nx = cx + dx[k];
int ny = cy + dy[k];
if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue; // 범위 벗어나면 넘어감
if (check[ny][nx] != 0) continue; // 방문했던적 넘어감
if (unions[ny][nx] == cu) continue; // 같은 섬도 넘어감
check[ny][nx] = check[cy][cx] + 1;
q.push(make_tuple(nx, ny, cu));
if (cu != unions[ny][nx] && unions[ny][nx] != 0)
{//만약 다음 섬을 찾았다면
//현재거리: check[cy][cx]
if (check[cy][cx] < answer) answer = check[cy][cx]; // 최소 거리 초기화
}
}
}
}
printf("%d\n", answer - 1);
//std::system("pause");
return 0;
}
[17471] 게리맨더링
- 난이도: 상
- 상당히.. 어려웠다.
- 문제를 이해하는데 10분, 풀이를 떠올리는데 30분, 구현 1시간, 나머지 디버깅으로 푸는데 총 3시간정도 걸린듯 하다.
- 일반적인 2차원 BFS만 주구장창 하다가 갑자기 맞닥뜨린 1차원 BFS에 살짝 멘붕이 왔다.
- 일반적인 그래프 문제..
- 어려운게 아니지만 익숙치 않다보니 상당히 어렵게 느껴졌다.
- 몇번 더 봐야할듯..
- 문제
- https://www.acmicpc.net/problem/17471
- 첫째 줄에 전체 구역의 개수 N, 둘째 줄에 각 구역 1번부터 N번까지 인원 수, 셋째 줄 부터 N째줄 동안 1번부터 N번까지 해당 노드와 연결된 노드 정보가 주어진다.
- 그룹은 항상 두개로 나뉘어야 하며, 한 그룹엔 최소 한 개의 노드를 갖는다.
- 전체 노드들을 두 그룹으로 나눈다.
- 나눠진 두 그룹의 모든 노드들은 서로 연결 되어있어야 한다.
- 나눠진 두 그룹 내의 인원수들을 모두 합한 뒤, 두 그룹 사이의 인원 수 최소 차이를 출력한다.
- 문제를 나누면
- 입력을 받는다.
- 두 그룹을 나눈다.
- 나눠진 두 그룹의 유효성을 검사한다.
- 모든 노드는 서로 연결되어 있는지 확인한다.
- 만약 나뉜 그룹이 유효하다면 노드 내 인원수를 계산하고 최솟값을 찾는다.
- 풀이
- 입력을 받는다.
- 두 그룹을 나눈다.
- 일반적인 DFS 알고리즘을 이용해 재귀적으로 나눌 수 있다.
- 나눌 때는 꼭 한 그룹에는 최소 한 노드가 있어야 한다.
- 따라서 전체 N개의 노드에 대해 1개부터 N/2개까지의 경우만 따지면 된다.
- 어차피 그 이상은 또 반복이니까..
- 나눠진 두 그룹의 유효성을 검사한다.
- 1차원 BFS를 이용한다.
- 첫 번째 그룹의 첫 번째 노드에서 연결된 노드들을 모두 check 한다.
- 이 때, 연결된 노드들이 다른 그룹에 속해있으면 check 하지 않는다
- 이런식으로 한 그룹의 전체 노드들에 대한 check 맵을 만든다.
- 만약 check 맵에 한 그룹의 어떤 노드 하나가 check 되어있지 않다면, 그 노드는 연결되어 있는 상태가 아니다.
- 따라서 유효하지 않은 그룹이다.
- 만약 두 노드가 모두 유효하다면 다음으로 넘어간다.
- 나뉜 그룹 내 인원수와 최솟값 계산
- 그냥 인원수만큼 더한담에 서로 뺀 값의 최솟값을 구한다.(절댓값)
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#define MAX 2147483647
using namespace std;
struct info
{
int members, group;
};
vector<info> town; // 그룹별 사람수, 선택여부
vector<int> connect[11]; // 그룹별 연결관계
int check[11]; // 체크 맵
int answer = MAX;
bool checker(int a, vector<int> group)
{//a가 group 안에있으면 true, 없으면 false 반환
bool answer = false;
for (int i = 0; i<int(group.size()); i++)
{
if (a == group[i])
{
answer = true;
break;
}
}
return answer;
}
bool validator(int N, vector<int> check_group, vector<int> other_group)
{ // check 그룹이 유효하면 true, 유효하지 않으면 false 반환
memset(&check, 0, sizeof(check)); // check 초기화
queue<int> q;
// 체크 그룹 첫번째 숫자 체크한다음 BFS
check[check_group[0]] = 1;
q.push(check_group[0]);
while (!q.empty())
{
int c = q.front();
q.pop();
for (int i = 0; i < connect[c].size(); i++)
{ // 현재 노드와 연결된 노드들동안
int n = connect[c][i]; // 다음 숫자는 체크 숫자와 연결된 노드
if (checker(n, other_group)) continue; //만약 다음 숫자 n이 다른 그룹에 있으면 넘어간다.
if (check[n] != 0) continue; //다음 숫자 체크되어있으면 넘어간다.
check[n] = 1; // 모두 만족한다면 체크한다.
q.push(n);
}
}
bool answer = true;
for (int i = 0; i<int(check_group.size()); i++)
{
if (check[check_group[i]] != 1)
{ // 만약 해당 그룹 숫자가 체크가 되어있지 않다면 연결된게 아니다.
answer = false; // 따라서 false
}
}
return answer;
}
void calc(int N, int num)
{
vector<int> group_a; // 해당 그룹 숫자 담기
vector<int> group_b;
for (int i = 0; i<int(town.size()); i++)
{
if (town[i].group == 1) group_a.push_back(i + 1);
else group_b.push_back(i + 1);
}
//생성된 그룹 유효성 검사
//그룹 유효성 검사
if (validator(N, group_a, group_b) && validator(N, group_b, group_a))
{//두 그룹 모두 유효한 그룹이라면
//그룹 a의 합
int sum_a = 0;
for (int i = 0; i<int(group_a.size()); i++)
{
sum_a += town[group_a[i] - 1].members;
}
//그룹 b의 합
int sum_b = 0;
for (int i = 0; i<int(group_b.size()); i++)
{
sum_b += town[group_b[i] - 1].members;
}
int dif = abs(sum_a - sum_b); // 절댓값 차
if (dif < answer) answer = dif; // 최솟값 비교
}
return;
}
void dfs(int idx, int cnt, int N, int num)
{
if (cnt == num)
{
// 골라진 노드들은 group=1로 초기화되어있음
calc(N, num);
return;
}
for (int i = idx; i < N; i++)
{ // 현재 인덱스부터 총 N까지 돈다.
if (town[i].group == 1)continue; // 만약 선택되어있다면 넘어간다.
town[i].group = 1; //선택하고
dfs(i + 1, cnt + 1, N, num); // 다음 번째 부터 참조한다.(중복방지)
town[i].group = 0; //선택해제
}
}
int main()
{
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
int temp;
scanf("%d", &temp);
town.push_back({ temp,0 });
}
for (int i = 1; i <= N; i++)
{
int nums;
scanf("%d", &nums);
for (int j = 0; j < nums; j++)
{
int temp;
scanf("%d", &temp);
connect[i].push_back(temp);
}
}
for (int n_group = 1; n_group <= int(N / 2); n_group++)
{
//고르기 및 연산
dfs(0, 0, N, n_group);
}
if (answer == MAX) answer = -1; // 못 나누는 경우 -1 출력
printf("%d\n", answer);
//std::system("pause");
return 0;
}