총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.
감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.
각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.
각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.
풀이
이 문제는 굉장히 간단한 문제이다. 입력은 다음과 같이 주어진다.
첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.
셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)
만약 시험장이 1,000,000개이고 응시자 수가 1,000,000에 B, C가 각각 1인 경우 최대로 필요한 감독관의 수는 10^12이 된다. 약 2*10^9까지 표현할 수 있는 int형으로는 부족하다. 따라서 64비트를 이용하는 long long형을 사용해야한다. 풀이는 너무 간단하다. 각 시험장의 응시자의 수에서 B를 빼고 남은 인원이 0보다 클 경우 a에 C-1을 더하고 C로 나눈 몫만큼의 부감독관이 필요하다. 자세히 설명하자면 아래와 같다.
만약 응시자 수에서 B를 뺀 값이 4라고 하자.
C의 값이 5라고 하면 1명의 부감독관만 필요하다.
4에 C-1인 4를 더하면 8이므로 5로 나눈 몫은 1이다.
만약 5명이 남았다고한다면 5에 C-1인 4를 더하면 9이고 이를 5로 나눈 몫은 그대로 1이다.
즉 나누려고하는 값에서 1을 뺀 값을 나눠지는 수에 더하고 나누면 소수점에서 올림을 할 수 있다.
소스 코드
#include <iostream>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
vector<int> arr;
int main() {
int N; cin >> N;
long long answer = 0; //정답
for(int i = 0; i < N; i++) {
int a; cin >> a;
arr.push_back(a);
}
int B, C; cin >> B >> C;
for(int a : arr) {
a -= B; //총감독관이 감시할 수 있는 인원 빼기
if(a > 0){ //그래도 수험생이 남아있으면
a += (long long)(C-1); //C-1을 더함
answer += (long long)(a / C); //C로 나눈 몫을 정답에 더하기
}
answer++; //총감독관 인원 더하기
}
cout << answer;
}
B를 뺀 값이 0보다 클 때 즉 수험생이 남아있는지 확인하는 이유는 만약 B를 뺀 값이 -5이고 C의 값이 4라고 한다면 C-1을 더하더라도 음수가 된다. 따라서 이상한 값이 나올 수 있기 때문이다.
이 문제는 정답 비율에 비해 쉽게 구현할 수 있는 문제이다. 문제는 간단하다. 뱀이 이동하며 사과를 먹으면 몸의 길이가 늘어난다. 문제에 설명이 부족하여 헷갈렸지만 1초에 1칸씩 움직인다고 생각하면 된다.
풀이
이 문제는 방향성을 가지고 있는 문제이다. 현재 진행 방향에서 좌회전하냐 우회전하냐의 문제를 쉽게 구현하기 위하여 아래와 같이 방향을 나타내는 배열을 이용하였다. dx, dy의 인덱스 값을 1 올릴 때마다 시계 방향으로 회전하고 반대로 1 내릴 때마다 반시계 방향으로 회전한다.
int dx[4] = {-1, 0, 1, 0}; //상, 우, 하, 좌 : 시계방향
int dy[4] = {0, 1, 0, -1};
뱀을 나타내기 위하여 앞 뒤로 좌표를 넣어야한다는 점에 딱 맞은 deque를 이용해야겠다고 생각했다. deque의 front는 뱀의 머리를, back은 뱀의 꼬리를 나타낸다. NxN 보드에서 1인 점은 사과가 있는 지점이고 -1인 곳은 뱀이 차지하고 있는 곳이다. 알고리즘은 다음과 같이 동작한다.
만약 머리가 향하는 다음 지점이 보드를 벗어날 경우 게임이 끝난지를 판단하는 fin변수를 true로 바꾸고 게임을 종료한다.
뱀을 나타내는 deque에 다음 지점의 좌표를 push_front하여 머리를 갱신해준다.
그렇지 않은 경우 만약 머리가 향하는 다음 지점에 사과가 없을 경우 꼬리부분을 pop_back하고 -1이었던 꼬리부분을 0으로 바꾸어준다.
그 다음 머리가 향한 다음 지점이 -1인 경우, 즉 뱀의 몸통을 만난 경우 fin변수를 true로 바꾸고 게임을 종료한다.
뱀의 머리가 향하는 다음 지점을 -1로 바꾼다.
왼쪽으로 회전하는 경우 방향을 나타내는 변수에 3을 더하고 4로 나눈 나머지를 다음 방향으로 정한다.
오른쪽으로 회전하는 경우 방향을 나타내는 변수에 1을 더하고 4로 나눈 나머지를 다음 방향으로 정한다.
방향을 모두 바꾼 다음에도 종료되지 않은 경우 벽을 만날 때까지 직진한다.
소스 코드
#include <iostream>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
int arr[101][101]; //보드 배열
int N, K, L;
int dx[4] = {-1, 0, 1, 0}; //상, 우, 하, 좌 : 시계방향
int dy[4] = {0, 1, 0, -1};
deque<pair<int,int>> snake; //뱀을 나타내는 deque
vector<pair<int,char>> info; //이동 시간과 위치 저장 벡터
int main() {
bool fin = false; //게임이 끝난지 판단하는 변수
int direction = 1; //현재 방향(오른쪽)
int answer = 0; //정답
int time = 0; //시간
snake.push_front({1, 1}); //현재 위치 뱀에 추가
arr[1][1] = -1; //뱀이 현재 있는 곳 표시
cin >> N >> K; //입력
for(int i = 0; i < K; i++) {
int a, b; cin >> a >> b;
arr[a][b] = 1;
}
cin >> L;
for(int i = 0; i < L; i++) {
int x; char c; cin >> x >> c;
info.push_back({x - time, c});
time = x;
}
for(pair<int, char> e : info) {
int x = e.first; //시간
char c = e.second; //다음 방향
while(!fin && x--) {
answer++; //시간 증가
int nx = snake.front().first + dx[direction]; //다음 x, y 좌표
int ny = snake.front().second + dy[direction];
if(nx < 1 || nx > N || ny < 1 || ny > N) { //벽에 닿은 경우 종료
fin = true;
break;
}
snake.push_front({nx, ny}); //뱀의 머리 갱신
if(arr[nx][ny] == 0) { //사과가 없는 경우
pair<int,int> back = snake.back(); //꼬리 제거
snake.pop_back();
arr[back.first][back.second] = 0; //보드에서 삭제
}
if(arr[nx][ny] == -1) { //뱀의 몸통을 만난 경우
fin = true; //게임 종료
break;
}
arr[nx][ny] = -1; //뱀의 머리 보드에 체크
}
if(c == 'L') //왼쪽으로 회전하는 경우
direction += 3;
else //오른쪽으로 회전하는 경우
direction++;
direction %= 4; //4개의 원소가 있으므로 범위를 벗어나지 않고 회전하게 만듦
}
while(!fin) { //방향 조절이 끝난 후 벽에 부딪힐 때까지 직진
answer++;
int nx = snake.front().first + dx[direction]; //다음 x, y 좌표
int ny = snake.front().second + dy[direction];
if(nx < 1 || nx > N || ny < 1 || ny > N) { //벽에 부딪힌 경우 종료
fin = true;
break;
}
snake.push_front({nx, ny}); //머리 갱신
if(arr[nx][ny] == 0) { //사과가 없는 경우
pair<int,int> back = snake.back(); //꼬리 제거
snake.pop_back();
arr[back.first][back.second] = 0;
}
if(arr[nx][ny] == -1) { //몸통을 만난 경우 종료
fin = true;
break;
}
arr[nx][ny] = -1; //뱀이 있으므로 체크
}
cout << answer; //정답 출력
}
이번 글에는 STL의 <queue> 헤더파일에 존재하는 내부 함수 우선순위 큐를 직접 구현해보았다. priority_queue를 C++ STL 홈페이지(https://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue)에서 찾아볼 경우 다음과 같이 나온다.
초록색 글씨를 보면 선언할 때 변수의 type(class도 가능)을 받고 두 번째 인자로 우선순위 큐를 구성하는 컨테이너, 즉 배열을 선언할 수 있다. 기본값으론 vector를 사용한다. 마지막 인자로 힙을 구성하는 비교 함수 연산자가 있는 class를 포함한다. 기본값인 less는 최대힙을 만들 때 사용한다. 최소힙으로 사용하고 싶을 경우 greater를 사용한다. 다음과 같이 최대힙, 최소힙을 선언할 수 있다.
우선순위 큐는 힙을 이용한다. FIRST IN FIRST OUT인 queue와 다르게 우선순위가 높은 인자가 우선적으로 나온다. 힙의 push와 pop은 다음과 같이 동작한다. 예시는 5, 6, 3, 7, 10, 4가 순서대로 push될 경우 최대힙이 만들어지는 과정이다.
힙은 언제나 완전 이진트리이다. 동작방식은 다음과 같다.
삽입
삽입하려는 값을 트리의 맨 마지막에 넣는다.
부모노드와 비교하며 삽입하려는 값이 더 큰 경우 부모노드와 값을 바꾼다.
삽입하려는 값보다 큰 값이 나오지 않을 때까지 반복한다.
만약 root노드보다 삽입하려는 값이 큰 경우 root노드에 저장한다.
삭제
트리의 맨 아래의 맨 오른쪽에 있는 원소인 pivot을 root노드로 위치시킨다.
왼쪽 자식 노드와 오른쪽 자식 노드 중 큰 값과 비교한다.
자식 노드가 더 큰 경우 자식노드와 값을 바꾼다.
pivot 값보다 작은 값을 만날 때까지 반복한다.
만약 leaf노드까지 도달한 경우 pivot 값을 leaf노드에 저장한다.
우선순위 큐는 위의 과정으로 동작한다. 여기서 비교하는 함수는 선언의 마지막 인자에 있는 class를 이용하여 비교연산을 한다.
priority_queue 코드 설명
class의 구조와 멤버 변수는 다음과 같다.
template <class T, class CONT = std::vector<T>, class CMP = less<typename CONT::value_type>>
class mypriority_queue {
private:
CONT container;
int num;
CMP compare;
}
맨 첫 번째 줄을 보면 글 맨 위에 있는 사진에서 확인할 수 있듯이 template를 동일하게 선언하였다. 타입, 컨테이터, 비교클래스.
멤버변수는 template로 선언한 container가 컨테이너, num은 원소의 수를 나타내고 compare는 비교를 실행할 인스턴스이다. 비교 클래스를 받기 때문에 클래스 안에 있는 비교함수나 연산자를 이용하기 위해선 그 class를 타입으로 가지는 인스턴스가 존재해야하기 때문에 선언하였다. 예를 들어 CMP안에 ()연산자가 정의된 경우 compare(a, b)와 같이 사용하여 비교연산을 수행할 수 있다.
사이트에 나와있는 멤버 함수는 다음과 같다.
이 중에 구현한 함수는 생성자를 포함해 empty, size, top, push, pop을 구현하였다. 다른 함수들은 많이 사용되지 않기 때문에 생략하였다.
처음 문제를 O(N)만에 풀 수 있는 방법을 생각해보았지만 뜻대로 되지 않고 자꾸 DFS를 이용하는 방법이 떠올라 DFS를 이용하지 않고 풀어보려했지만 결국 DFS를 사용하게 되었다. 이 문제가 까다로운 부분은 원형으로 연결되어 있다는 것이다. 1차원 배열의 맨 끝에서 오른쪽으로 한 번 더 이동하면 첫 번째 원소에 와야하는 것과 같은 예외처리를 해야한다. 문제는 다음과 같이 풀었다.
DFS를 이용하여 임의의 취약지점에서 출발한다.
점검할 수 있는 취약지점까지 점검한다.
다음 취약지점부터 아직 점검하지 않은 친구가 점검할 수 있는 거리만큼 점검한다.
만약 점검한 취약지점 수와 전체 취약지점 수가 같은 경우 결과값을 최소값으로 갱신한다.
소스 코드
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int answer = 1e9; //정답 최대값으로 설정
int N;
vector<bool> dvisit; //점검을 완료한 친구 표시
void dfs(int ans, int now, int len, int total, vector<int> &weak, vector<int> &dist) {
int start = weak[now]; //시작 취약지점
int limit = weak[now] + dist[len]; //점검할 수 있는 거리의 마지노선
int cnt = 0; //점검한 취약지점 수
if(limit >= N) { //만약 범위를 벗어나 다시 0부터 시작하는 경우
while(true) {
if((weak[now] >= start) || (weak[now] <= (limit % N))) { //다음 탐색할 취약지점이 점검할 수 있는 범위에 있는 경우
now++; //다음 취약지점으로 이동
now %= weak.size(); //범위 벗어나지 않게 처리
cnt++; //점검한 취약지점 수 증가
if(cnt + total == weak.size()) { //취약지점 모두 점검한 경우
answer = min(answer,ans); //최소값 갱신
return; //리턴
}
}
else { //범위를 벗어난 경우 점검 종료
break;
}
}
}
else { //만약 범위를 벗어나지 않는 경우
while(true) {
if((weak[now] >= start) && (weak[now] <= limit)) { //다음 탐색할 취약지점이 점검할 수 있는 범위에 있는 경우
now++; //다음 취약지점으로 이동
now %= weak.size(); //범위 벗어나지 않게 처리
cnt++; //점검한 취약지점 수 증가
if(cnt + total == weak.size()) { //취약지점 모두 점검한 경우
answer = min(answer,ans); //최소값 갱신
return; //리턴
}
}
else { //범위를 벗어난 경우 점검 종료
break;
}
}
}
for(int d = 0; d < dist.size(); d++) { //점검할 다음 친구 선택
if(dvisit[d]) continue; //이미 점검한 친구는 패스
dvisit[d] = true; //방문표시
dfs(ans+1 , now, d, total + cnt, weak, dist); //DFS를 이용하여 now부터 취약지점 점검
dvisit[d] = false; //방문표시 취서
}
}
int solution(int n, vector<int> weak, vector<int> dist) {
N = n; //외벽길이 전역변수로 저장
dvisit.resize(dist.size()); //방문배열 크기 설정
sort(dist.begin(), dist.end(), greater<int>()); //큰 것부터 정렬
for(int w = 0; w < weak.size(); w++) { //점검을 시작할 취약지점 위치
for(int d = 0; d < dist.size(); d++) { //점검할 친구 선택
dvisit[d] = true;
dfs(1, w, d, 0, weak, dist);
dvisit[d] = false;
}
}
if(answer == 1e9) return -1; //모두 탐색하지 못한 경우 -1 리턴
else return answer; //그렇지 않은 경우 최소값 리턴
}
최대한 반복되는 비교를 하지 않도록 방문함수를 설정하고 점검한 취약지점을 다시 점검하도록 하지 않도록 다음 취약지점으로 이동하며 점검하도록 프로그램을 짜보았다. DFS함수의 인자가 많은 것이 아쉬운 부분이지만 다른 방법으로는 떠오르지 않아 함수의 인자 밖에 선택할 수 없었다. weak와 dist를 모두 전역변수로 하면 메모리 낭비와 복사하는 시간이 걸리므로 call by reference를 이용하여 그런 시간을 줄여보았다.
이 문제는 DFS, BFS 모두 풀이가 가능한 문제이다. 글쓴이는 평소 DFS를 많이 이용했기 때문에 이번에는 BFS를 이용하여 풀어보았다. 로봇이 한 칸을 차지하는 것이 아닌 두 칸을 차지하므로 예외처리를 많이 해야하기 때문에 캐치하지 못한 부분이 있어 일부 테스트 케이스를 통과하지 못할 수도 있다. 나도 이 문제를 풀며 내가 생각하지 못한 부분을 예외처리하지 못하여 약간의 시간이 더 걸렸다. 로봇의 현재 위치에서 생각해야할 부분은 네 가지가 있다.
다음 위치가 보드를 벗어나는지
로봇이 차지하는 두 칸 중 하나도 1이 아닌지
이미 현재 위치를 거쳐갔는지
회전하는 경우 회전할 때 지나가는 칸이 1이 아닌지
위 네 가지만 예외처리하면 쉽게 풀 수 있는 문제이다. 예외처리만 하면 되는 문제이기 때문에 if, continue 등이 많이 쓰였다.
문제를 풀 때 로봇이 상하좌우로 이동하는 경우, 회전하는 경우를 나누어서 풀었다. 상하좌우로 이동하는 경우는 일반 BFS처럼 풀면 되기 때문에 예외처리가 따로 할 부분이 없었다. 문제는 회전하는 경우였다. 회전하는 경우를 차지하는 두 칸 중에 한 칸이 대각선으로 이동하는 방식으로 생각했다. 그림으로 나타내면 다음과 같다.
위와 같이 이동한다고 할 때 실제로는 2, 4번으로 이동할 수 있지만 1, 3번으로는 이동하지 못한다. 이 부분을 예외처리하기 위해 두 칸의 x좌표나 y좌표 중 하나가 같은 경우에만 올바르게 회전했다고 판단했다. 이 과정을 다른 쪽 칸도 똑같이 진행하였다. 이렇게 회전하는 경우에 갈 수 있는 좌표의 위치를 계산할 수 있다.
소스 코드
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct pos{ //x, y좌표를 가지는 구조체
int x, y;
};
struct element { //큐에 넣을 구조체
pair<pos,pos> position;
int depth;
};
bool visit[101][101][101][101]; //방문배열
int dx[4] = {1, 0, 0, -1}; //dx, dy는 상하좌우로 이동
int dy[4] = {0, 1, -1, 0};
int rx[4] = {1, 1, -1, -1}; //rx, ry는 회전
int ry[4] = {1, -1, 1, -1};
int solution(vector<vector<int>> board) {
int N = board.size();
pair<pos,pos> robot = {{0, 0}, {0, 1}}; ///로봇의 현재 위치
queue<element> q; //BFS에 사용될 큐
q.push({robot, 0}); //현재 위치를 큐에 넣음
visit[robot.first.x][robot.first.y][robot.second.x][robot.second.y] = true; //현재 위치 방문 표시
visit[robot.second.x][robot.second.y][robot.first.x][robot.first.y] = true; //두 칸을 반대로 했을 때도 방문 표시
while(!q.empty()) { //큐가 빌 때까지
element e = q.front(); q.pop();
pair<pos,pos> now = e.position; //현재 위치
for(int d = 0; d < 4; d++) { //상하좌우 방향으로
pair<pos,pos> nxt = {{now.first.x + dx[d], now.first.y + dy[d]}, {now.second.x + dx[d], now.second.y + dy[d]}}; //다음 좌표 위치
if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 건너뛰기
if(nxt.first.y < 0 || nxt.first.y >= N) continue;
if(nxt.second.x < 0 || nxt.second.x >= N) continue;
if(nxt.second.y < 0 || nxt.second.y >= N) continue;
if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //만약 두 칸 중에 하나라도 1인 경우 건너뛰기
if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue; //이미 방문한 경우도 건너뛰기
if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue; //로봇 왼쪽 오른쪽이 반대로 됐을 경우도 같음
if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //도착한 경우 방문 횟수 리턴
return e.depth + 1;
}
else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
q.push({nxt, e.depth + 1});
}
}
for(int r = 0; r < 4; r++) { //회전하는 경우
pair<pos,pos> nxt = {{now.first.x + rx[r], now.first.y + ry[r]}, {now.second.x, now.second.y}}; //한 쪽 날개 회전
if(nxt.first.x != nxt.second.x && nxt.first.y != nxt.second.y) continue; //만약 한쪽을 대각선으로 회전했을 때 로봇이 차지하는 두 칸이 나란히 있지 않은 경우 건너뛰기
if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 건너뛰기
if(nxt.first.y < 0 || nxt.first.y >= N) continue;
if(nxt.second.x < 0 || nxt.second.x >= N) continue;
if(nxt.second.y < 0 || nxt.second.y >= N) continue;
if(board[now.first.x][now.first.y + ry[r]] || board[now.first.x + rx[r]][now.first.y]) continue; //회전시 지나가는 칸이 1인 경우 건너뛰기
if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //차지하는 두 칸중 하나라도 1인 경우 건너뛰기
if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue; //이미 방문한 경우 건너뛰기
if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue;
if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //종료지점 도착시 리턴
return e.depth + 1;
}
else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
q.push({nxt, e.depth + 1});
}
}
for(int r = 0; r < 4; r++) { //다른 한 쪽이 회전하는 경우
pair<pos,pos> nxt = {{now.first.x, now.first.y}, {now.second.x + rx[r], now.second.y + ry[r]}}; //다른 한 쪽 날개 회전
if(nxt.first.x != nxt.second.x && nxt.first.y != nxt.second.y) continue; //로봇이 차지하는 두 칸이 나란히 있지 않은 경우 리턴
if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 리턴
if(nxt.first.y < 0 || nxt.first.y >= N) continue;
if(nxt.second.x < 0 || nxt.second.x >= N) continue;
if(nxt.second.y < 0 || nxt.second.y >= N) continue;
if(board[now.second.x][now.second.y + ry[r]] || board[now.second.x + rx[r]][now.second.y]) continue; //회전시 지나가는 칸이 1인 경우 건너뛰기
if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //차지하는 두 칸중 하나라도 1인 경우 건너뛰기
if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue;//이미 방문한 경우 건너뛰기
if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue;
if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //종료지점 도착시 리턴
return e.depth + 1;
}
else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
q.push({nxt, e.depth + 1});
}
}
}
}
같은 코드가 반복되어 비효율적인 부분이 있긴 하지만 프로그램 자체가 길지 않으므로 하나의 함수에 작성하였다.시간의 효율성을 생각해보면 큐 안의 반복문이 4번 반복하는 for문이 3개 있으므로 배열의 크기를 N이라고 할 때 약 N * N * 12번의 반복이 발생하지만 12번의 반복은 10^8이 약 1초 걸린다고 생각할 때 무시해도 될 정도의 아주 작은 시간이므로 그다지 효율성을 떨어뜨리지 않는다고 할 수 있다.
이 문제는 LIS를 이용해 풀면 쉽게 풀 수 있는 문제이다. 우선 왼쪽 전봇대에 연결된 위치 순서의 오름차순으로 정렬한다. 하나의 위치에 하나의 전깃줄만 연결되어 있으므로 중복되는 번호는 존재하지 않는다. 그렇다면 이제부터 오른쪽 전봇대에 연결된 위치만 생각하면 된다. 오른쪽 전봇대에 연결된 위치의 번호의 LIS의 최대 길이가 전깃줄을 최소로 제거하는 방법이다. 그림으로 보면 아래와 같다.
파란색 선이 꼬이지 않고 최대로 연결한 방법이고 빨간 선이 삭제해야하는 전깃줄이다. 번호를 보면 왼쪽 번호가 증가함에 따라 오른쪽 번호도 당연히 증가하는 것을 알 수 있다. 만약 오른쪽 번호가 증가하다 감소하면 전깃줄이 꼬였다는 이야기이다. 따라서 이 문제는 왼쪽 전봇대의 번호 순으로 정렬한 다음 오른쪽 전깃줄 번호의 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 코드는 다음과 같다.
소스 코드
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int,int>> arr;
vector<int> dp;
bool cmp(pair<int,int> a, pair<int,int> b) { //왼쪽 전봇대 번호 정렬
return a.first < b.first;
}
int main() {
int N; cin >> N;
for(int i = 0; i < N; i++) {
int a, b; cin >> a >> b;
arr.push_back({a,b});
}
sort(arr.begin(), arr.end(), cmp); //정렬
dp.push_back(-1); //초기값 설정
for(int i = 0; i < N; i++) { //LIS 최대 길이 구하기
if(dp.back() < arr[i].second) { //가장 큰 원소보다 큰 경우 뒤에 push
dp.push_back(arr[i].second);
}
else { //그렇지 않은 경우 이진탐색을 이용하여 알맞은 위치에 교체
auto it = lower_bound(dp.begin(), dp.end(), arr[i].second);
*it = arr[i].second;
}
}
cout << N - (dp.size()-1); //총 개수 N에서 최대 LIS 길이를 뺀 수만큼 전깃줄 제거해야함
}
이 문제는 이전 글에서 다루었던 가장 긴 증가하는 부분 수열(https://shyeon.tistory.com/52)에서 사용한 DP를 이용할 경우 시간 복잡도가 O(n^2)이 걸리므로 이 문제의 최대 길이인 10^6이 주어질 경우 10^12으로 시간제한인 1초를 훌쩍 넘게 된다. 따라서 이 문제는 O(N * log N)이 걸리는 알고리즘 방식을 이용해야한다.
이 알고리즘은 가장 현재까지 탐색한 수열 중 가장 긴 수열의 길이를 가진 배열을 항상 유지한다. 만약 배열의 맨 마지막 원소 즉 가장 큰 값보다 클 경우 배열 맨 뒤에 붙여준다. 그렇지 않을 경우 현재 위치의 원소가 그 배열에서 위치할 수 있는 곳을 이진탐색을 이용하여 찾고 그 위치의 원소와 바꾼다. 예시를 이용하여 다시 설명하겠다.
예제
위 예제를 풀이한 알고리즘 순서대로 풀어보겠다. 처음 원소는 음수의 무한대로 초기화한다. 따라서
-INF
-INF 10 (맨 끝에 추가)
-INF 10 20 (맨 끝에 추가)
-INF 10 20 (10자리에 10이 들어갈 수 있음)
-INF 10 20 30 (맨 끝에 추가)
-INF 10 20 30 (20 자리에 10 교체)
-INF 10 20 30 50 (맨 끝에 추가)
위의 예시는 반복되는 숫자가 있으므로 다른 예시로 한 번 더 해보겠다.
예시 : 10 20 40 30 70 90 50 60 80
-INF
-INF 10
-INF 10 20
-INF 1020 40
-INF 10 30 40
-INF 10 30 40 70
-INF 10 30 40 70 90
-INF 10 30 40 50 90
-INF 10 30 40 50 60
-INF 10 30 40 50 60 80
이런 식으로 진행된다. 따라서 마지막 크기에서 -1을 해주면 가장 긴 수열의 길이를 구할 수 있다. 마지막에는 가장 긴 수열이 저장되는 것은 아니지만 길이는 이 방법을 이용하여 O(N log N)으로 구할 수 있다.
소스 코드
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MN = 1001;
const int INF = 1e9; //무한대
vector<int> dp;
int main() {
int N; cin >> N;
dp.push_back(-INF); //마이너스 무한대 push
for(int i = 0; i < N; i++) {
int a; cin >> a; //입력 받아서
if(dp.back() < a) { //배열의 맨 마지막 원소보다 크면 뒤에 저장
dp.push_back(a);
}
else { //그렇지 않을 경우
auto it = lower_bound(dp.begin(), dp.end(), a); // 이진탐색을 이용하여 들어갈 수 있는 위치 탐색
*it = a; //해당 위치에 교체
}
}
cout << dp.size() - 1; // -무한대 빼고 길이 출력
}
문제는 간단하다 수열이 주어졌을 때 수열의 순서를 바꾸지 않고 증가하는 부분 수열로 가장 긴 길이를 출력하는 문제이다.
이 문제는 DP를 이용하여 풀 수 있다. 이 알고리즘을 DP를 이용하여 해결하는 데에는 O(n^2)의 시간 복잡도를 가진다. 브루트 포스 방식으로 i번째 인덱스부터 끝까지 증가하는 수열의 길이를 찾고 가장 긴 길이를 출력하면 된다.
소스 코드
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MN = 1001;
int dp[MN];
int arr[MN];
int main() {
int N; cin >> N; //길이 입력
int res = 0; //최대 길이 저장
for(int i = 0; i < N; i++) //수열 입력
cin >> arr[i];
for(int i = 0; i < N; i++) { //i번째 인덱스까지
dp[i] = 1; //원소 1개의 길이는 1
for(int j = 0; j < i; j++) { //i번째 인덱스까지
if(arr[i] > arr[j]) { //증가하는 수열이면
dp[i] = max(dp[i], dp[j] + 1); //i번째 인덱스까지 최대길이 갱신
}
}
res = max(res, dp[i]); //최대 길이 저장
}
cout <<res;
}
이 문제는 dp를 이용하여 i번째 인덱스까지 만들어지는 수열 중 증가하는 수열의 최대 길이만 갱신하는 방식이다. 이 방법의 아쉬운 점은 가장 긴 증가하는 부분 수열 자체를 구할 수는 없다. 또 이 알고리즘은 O(n^2)의 시간 복잡도를 가지는 것이 굉장히 아쉬운 부분이다. 다른 방식을 사용하면 O(N * log N)으로 해결할 수 있다. 이 방식은 가장 긴 증가하는 부분 수열 2에서 다루도록 하겠다.
