총 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; //정답 출력
}
이 문제는 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에서 다루도록 하겠다.
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
예제
풀이
이 문제는 이분 탐색으로 접근해야 하는 문제이다. 이분 탐색으로 푸는 문제는 문제 내용에서 힌트를 얻을 수 있다. 이분 탐색 문제는 최대나 최소를 구하는 문제가 많이 나온다. 이 문제도 "C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오."라고 나와있다. 이 부분에서 이분탐색을 이용해야한다는 것을 알아차릴 수 있다.
이 문제에서 mid로 설정해야할 값은 공유기 사이의 거리이다. 즉 mid보다 큰 차이가 나면 공유기를 하나 설치해야한다는 것이다. 따라서 설치해야하는 공유기의 수를 매번 계산하여 C개의 공유기가 설치될 때의 최대값을 구할 수 있다.
소스 코드
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
vector<int> arr;
int main() {
int N, C; cin >> N >> C;
for(int i = 0; i < N; i++) {
int a; cin >> a;
arr.push_back(a);
}
sort(arr.begin(), arr.end());
int left = 1, right = arr[arr.size() - 1] + 1;
for(int i = 0; i < 30; i++) {
int mid = (left + right) / 2;
int pos1 = arr.front();
int pos2;
int wifi = 1;
for(int j = 1; j < arr.size(); j++) {
pos2 = arr[j];
int dist = pos2 - pos1;
if(dist >= mid) {
wifi++;
pos1 = pos2;
}
}
if(wifi >= C)
left = mid;
else
right = mid;
}
cout << left;
}
문제에서 죄표의 최대 값은 10^9이다. 이 값은 2^30보다 작은 값이므로 이분 탐색을 하였을 때 30번만 반복한다면 충분히 커버할 수 있다. 초기 left 값은 1, right값은 가장 큰 인덱스에 1을 더한 값이다. 1을 더한 이유는 정답은 left인데 만약 마지막 인덱스가 정답일 경우 left가 도달하지 못할 수 있기 때문이다. 이 문제는 조건을 만족하는 최대값을 구하는 문제이므로 공유기의 수가 C와 같을 경우에도 left에 mid값을 넣어준다. 그렇다면 C와 같을 때에도 left값은 이를 만족하는 조건에서의 최대 값을 가질 수 있다.
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력 예시
풀이
이 문제는 방문 빨간 공과 파란 공의 위치가 바뀌었을 때 정확히 어디에 위치하는지를 잘 계산하여야한다. 문제를 본 순간 DFS를 이용하여 풀어야겠다고 생각하였다. 하지만 BFS를 이용하면 더 간단한 풀이가 가능했다. 직접 구현한 코드는 DFS를 이용하였다. DFS를 이용하여 빨간 공, 파란 공이 상하좌우로 기울어졌을 때 멈추는 지점을 계산하였고 공이 동시에 빠지는 지를 판단하였다. 파란 공만 빠지는 경우를 생각해야하므로 파란 공을 먼저 생각하였다. 코드의 실행은 다음과 같다.
파란 공이 멈출 때까지 한 방향으로 이동한다.
만약 파란 공이 구멍에 빠진 경우 다른 방향으로 계속한다.
만약 빨간 공이 부딪힌 경우 체크한다. (만약 빨간공이 구멍에 빠질 경우 같이 빠질 수 있고 빨간 공이 멈춘 경우 빨간 공 옆에 멈출 것이기 때문에 지금 위치를 판단할 수 없다)
파란공이 멈춘 위치를 저장하고 빨간공과 부딪히지 않은 경우에만 위치를 배열에서 수정(부딪힌 경우 빨간공에 의해 위치가 결정되므로)
빨간 공이 멈출 때까지 같은 방향으로 이동한다.
만약 구멍에 빠졌을 경우
아까 체크한 파란공이 빨간공과 부딪힌 경우는 파란 공을 원래 위치로 되돌리고 계속 무시
체크되지 않을 경우 depth가 최소값인 경우 정답을 갱신하고 다른 방향으로 계속
빨간 공이 멈춘 위치를 저장하고 빨간공 위치를 배열에서 수정
만약 파란 공이 빨간 공과 부딪힌 경우 파란공 위치를 다 빨간공 옆으로 수정하고 배열에서도 위치 수정
DFS로 수정된 빨간 공과 파란 공을 탐색 계속
만약 현재 빨간 공과 파란 공의 위치가 이전에 방문했을 때의 회전 횟수보다 많은 경우는 리턴하여 불필요한 재탐색을 하지 않는다.
그렇지 않은 경우 현재 빨간 공, 파란 공의 위치일 때의 회전 횟수를 갱신하고 탐색을 계속한다.
탐색이 끝난 경우 빨간 공, 파란 공 위치를 다시 되돌리고 다른 방향으로 계속한다.
위 실행 순서를 구현한 코드이다.
코드
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int MN = 11;
string arr[MN];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
int visit[MN][MN][MN][MN];
int ans = 11;
void dfs(pair<int,int> red, pair<int,int> blue, int depth) {
if(depth > 10) return; //10번 이상 움직인 경우 리턴
int redx = red.first, redy = red.second;
int bluex = blue.first, bluey = blue.second;
if(visit[redx][redy][bluex][bluey] <= depth) return; //이미 방문한 경우 리턴
visit[redx][redy][bluex][bluey] = depth;
for(int d = 0; d < 4; d++) { //네 가지 방향으로
pair<int,int> nblue; //파란공 이동
int nx = bluex + dx[d]; //다음 파란공 위치
int ny = bluey + dy[d];
bool chk = false; //빨간공과 부딪히는지 여부 판단
while(arr[nx][ny] == '.') { //멈출 때까지
nx += dx[d];
ny += dy[d];
}
if(arr[nx][ny] == 'O') continue; //파란 공이 구멍에 빠진 경우 계속
if(arr[nx][ny] == 'R') { //만약 빨간 공을 부딪힌 경우
chk = true; //부딪혔다고 표시
}
nx -= dx[d]; //멈춘 곳으로 위치
ny -= dy[d];
nblue = {nx, ny}; //파란공 위치 저장
if(!chk) { //부딪히지 않았을 경우에만 수정
arr[bluex][bluey] = '.'; //파란공 위치 수정
arr[nx][ny] = 'B';
}
pair<int,int> nred; //빨간공 이동
nx = redx + dx[d]; //다음 빨간공 위치
ny = redy + dy[d];
while(arr[nx][ny] == '.') { //멈출 때까지
nx += dx[d];
ny += dy[d];
}
if(arr[nx][ny] == 'O') { //구멍에 빠진 경우
if(!chk) {//파란 공이 같이 빠지지 않을 경우에만 정답 갱신
ans = min(ans, depth+1);
arr[nblue.first][nblue.second] = '.'; //파란 공 위치 원래대로 돌리고 계속
arr[bluex][bluey] = 'B';
}
continue;
}
nx -= dx[d]; //빨간공 멈춘 곳으로 저장
ny -= dy[d];
nred = {nx, ny}; //빨간공 위치 저장
arr[redx][redy] = '.'; //빨간공 위치 수정
arr[nx][ny] = 'R';
if(chk) { //만약 파란공이 빨간공과 부딪힌 경우
nblue.first = nx - dx[d]; //파란공 위치를 빨간공 옆으로 수정
nblue.second = ny - dy[d];
arr[nblue.first][nblue.second] = 'B'; //파란공 위치 표시
arr[bluex][bluey] = '.';
}
dfs(nred, nblue, depth+1); //dfs로 탐색 계속
arr[nred.first][nred.second] = '.'; //빨강, 파란공 위치 처음으로 되돌리기
arr[nblue.first][nblue.second] = '.';
arr[redx][redy] = 'R';
arr[bluex][bluey] = 'B';
}
}
int main() {
int N, M; cin >> N >> M;
fill(&visit[0][0][0][0], &visit[MN-1][MN-1][MN-1][MN], 11); //방문 배열 초기화
pair<int,int> red;
pair<int,int> blue;
for(int i = 0; i < N; i++) {
cin >> arr[i];
for(int j = 0; j < arr[i].size(); j++) {
if(arr[i][j] == 'R') { //빨간공 위치 저장
red = {i, j};
}
if(arr[i][j] == 'B') { //파란공 위치 저장
blue = {i, j};
}
}
}
dfs(red, blue, 0);
if(ans > 10) cout << -1; //10번 이상 걸린 경우 -1출력
else cout << ans; //그렇지 않은 경우 걸린 횟수 출력
}
복잡해보이고 눈에 확 들어오는 코드는 아니지만 스스로 판단하기에 메모이제이션을 이용해 불필요한 탐색을 줄였다고 생각한다.
생각하지 못한 반례들이 꽤 있어서 질문검색에 있는 반례들을 많이 참고하였다. 빨간공의 좌표, 파란공의 좌표를 출력해보며 잘못 된 부분을 고쳐보며 스스로 풀 수 있었다. 이 문제의 티어는 골드2로 꽤 높은 편이다. 이러한 문제를 많이 풀어봐야할 것 같다.
이 문제는 DFS나 BFS로 간단히 풀 수 있는 문제처럼 보인다. 하지만 기본적인 DFS나 BFS로 풀 경우 시간초과가 발생한다. 따라서 DFS와 DP를 결합한 메모이제이션 방식을 이용해야한다. 그렇다면 메모이제이션을 어떻게 사용해야할까?
예시
입력 배열
만약 (0,0)인 5에서 시작한다면 5, 6, 7, 8, 9, 15까지 탐색 가능하며 2차원인 DP배열은 다음과 같을 것이다.
DP 배열
5에서 시작하면 총 7번까지 탐색 가능하다. 만약 그렇다면 (1,0)인 3에서 탐색을 시작한다면 어떻게 될까? 3에서는 5방향으로 탐색한다면 5에서 시작한 것과 똑같이 탐색할 것이다. 5부터는 결과도 똑같을 것이다. 그렇다면 3은 5에 이미 탐색한 결과가 있을 경우 DP배열의 (0,0)에 1을 더해주기만 하면 탐색 가능한 최대값을 얻을 수 있을 것이다. 만약 그렇지 않고 5부터 다시 탐색한다면 같은 반복을 여러번할 것이다. 만약 3부터 탐색하고 (1,1)인 2부터 탐색한다면 같은 작업을 3번 반복하는 것이다. 엄청난 시간낭비가 발생한다. 그렇기 때문에 이미 계산한 결과가 있는 경우 탐색을 멈추고 그 결과값을 이용해야한다. 코드로 나타내면 다음과 같다.
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MN = 501;
int dp[MN][MN]; //DP 배열
int arr[MN][MN]; //입력 배열
bool visit[MN][MN]; //방문 배열
int N;
int di[4] = {1, 0, 0, -1}; //상하좌우 표시
int dj[4] = {0, 1, -1, 0};
int dfs(int i, int j) {
if(visit[i][j]) return dp[i][j]; //만약 이미 계산한 결과값이 있는 경우 사용
visit[i][j] = true; //방문 표시
dp[i][j] = 1; //첫 방문인 경우 1로 초기화
for(int d = 0; d < 4; d++) { //상하좌우를 탐색
int ni = i + di[d];
int nj = j + dj[d];
if(ni >= 0 && ni < N && nj >= 0 && nj < N) { //배열 범위를 벗어나지 않는 조건
if(arr[ni][nj] > arr[i][j]) //더 많은 대나무가 있는 곳으로
dp[i][j] = max(dp[i][j],dfs(ni, nj) + 1); //탐색하고 최대값 갱신
}
}
return dp[i][j]; //현 위치에서의 최대값 리턴
}
int main() {
cin >> N;
int ans = 1;
for(int i = 0; i < N; i++) { //입력받기
for(int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
ans = max(ans,dfs(i, j)); //각 위치에서 시작하여 최대값 갱신
}
}
cout << ans; //최대값 출력
return 0;
}
DFS와 DP를 이용하여 불필요한 재방문을 스킵하면 시간을 줄일 수 있다. 메모이제이션은 DP가 어떤 값을 기억하는지를 정확히 알고 이해해야지 사용할 수 있다. 카카오 코딩테스트에서도 가끔 메모이제이션을 사용하는 문제가 나오기 때문에 이런 문제를 많이 풀어보는 것이 중요하다.
