문제 설명
https://programmers.co.kr/learn/courses/30/lessons/60062
레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.
레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.
외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.
제한사항
- n은 1 이상 200 이하인 자연수입니다.
- weak의 길이는 1 이상 15 이하입니다.
- 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다.
- 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다.
- weak의 원소는 0 이상 n - 1 이하인 정수입니다.
- dist의 길이는 1 이상 8 이하입니다.
- dist의 원소는 1 이상 100 이하인 자연수입니다.
- 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return 해주세요.
입출력 예
| 12 | [1, 5, 6, 10] | [1, 2, 3, 4] | 2 |
| 12 | [1, 3, 4, 9, 10] | [3, 5, 7] | 1 |
입출력 예에 대한 설명
입출력 예 #1
원형 레스토랑에서 외벽의 취약 지점의 위치는 다음과 같습니다.
친구들을 투입하는 예시 중 하나는 다음과 같습니다.
- 4m를 이동할 수 있는 친구는 10m 지점에서 출발해 시계방향으로 돌아 1m 위치에 있는 취약 지점에서 외벽 점검을 마칩니다.
- 2m를 이동할 수 있는 친구는 4.5m 지점에서 출발해 6.5m 지점에서 외벽 점검을 마칩니다.
그 외에 여러 방법들이 있지만, 두 명보다 적은 친구를 투입하는 방법은 없습니다. 따라서 친구를 최소 두 명 투입해야 합니다.
풀이
아무래도 반복된 계산을 통한 결과의 도출이라 판단하여, 문제풀이의 큰 방식은 재귀호출로 구현하였다. 하나의 함수에서 흐름은 기저조건(basecase)을 먼저 검사한 후에, 해당 함수의 인자인 dist 벡터 속 최대값을 가져온 후 length 인자로 지정, 이후 해당 값을 제외한 새로운 dist 벡터인 nextDist 벡터를 만든다.
이후 반복문을 통해 계산을 진행하는데, 우선 weak 벡터의 한 요소를 특정 위치로 잡은 후 length 만큼의 길이안에 포함되어 있지 않는 요소들로만 이루어진 새로운 nextWeak 벡터를 만든다. 이후 이렇게 만든 벡터를 가지고 새로운 재귀호출 함수의 인자로 넘긴다.
앞서 함수를 만드는 데 적용한 가정이 있다면, 우선 최소로 친구를 투입하기 위해선 dist 벡터의 최대값들을 계속 사용해야 한다고 고려했고, 특정 위치를 잡는데 있어 단순히 원형 레스토랑의 모든 위치를 반복문으로 접근하는 것이 아닌 기존 weak 벡터의 요소들만을 특정 위치로 사용했다는 점과, 시계 방향과 반시계 방향으로 케이스를 나누지 않고 오로지 시계 방향으로만 계산을 적용했다는 점이다.
이후 기저조건으로는, 만약 인자로 받은 weak 배열의 size가 0이라면 모든 취약한 점을 다 찾은 것이라 판단하여 그 때의 count 값을 answer와 비교하여 답을 대입하거나 단순 함수를 종료한다. 또는 기존 count가 이미 답에 근접했거나, 사용하려는 dist 벡터의 size가 0이라면 더 이상 계산을 진행할 수 없다 판단하여 함수를 종료한다.
재귀호출을 줄이기위한 수정
아무래도 재귀호출이다 보니 초반 코드를 적용했을 때 시간이 너무 오래걸리고 시간 초과로 통과하지 못한 케이스까지 존재하여, 재귀호출 횟수 자체를 최대한 줄이기 위해 여러 제한을 적용하였다.
- 기저조건의 종료 조건에서 count==answer가 아닌 count==answer - 1을 적용하였다. 이는 만약 해당 기저조건을 통과하더라도 어짜피 계산을 통해 count가 증가하기에, 우선 값이 하나 작더라도 함수를 종료한다.
- 함수에서 계산을 끝낸 후 재귀호출을 부를 때도 nextWeak 벡터의 크기를 가지고 최대한 적은 재귀호출 함수를 부르게 작성했다. 작성한 함수 방식이 하나의 재귀호출 함수가 단 하나의 재귀호출 함수를 부르는 것이 아닌 여러 함수를 부르는 방식이기에, 이를 줄이기 위해선 해당 함수에서 최대한 많이 weak 벡터를 줄였을 때만 다음 재귀호출 함수를 부를 수 있게 적용하였다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void check(int n, vector<int> weak, vector<int> dist, int count, int& answer) { //재귀호출
int length;
int minNextWeakSize = 15;
vector<int> nextDist;
if (weak.size() == 0) {//종료조건
if (count < answer)
answer = count;
return;
}
if (count == answer - 1 || dist.size() == 0)//종료조건
return;
length = dist[dist.size() - 1];//현재 함수에서 사용할 길이는 가장 큰 길이
nextDist.assign(dist.begin(), dist.end() - 1);//새로운 dist벡터 생성
for (int i = 0; i < weak.size(); i++) {//전체 weak에 대해 반복
vector<int> nextWeak;
int pos = weak[i];
if (pos + length >= n) {//위치부터 길이만큼이 n을 넘어선 경우
for (int j = 0; j < weak.size(); j++) {//새로운 weak벡터 생성
if ((pos + length) % n < weak[j] && weak[j] < pos)
nextWeak.push_back(weak[j]);
}
}
else {//위치부터 길이만큼이 n보다 작을 경우
for (int j = 0; j < weak.size(); j++) {//새로운 weak벡터 생성
if (!(pos <= weak[j] && weak[j] <= pos + length))
nextWeak.push_back(weak[j]);
}
}
if (nextWeak.size() <= minNextWeakSize) {//재귀호출 제한
minNextWeakSize = nextWeak.size();
check(n, nextWeak, nextDist, count + 1, answer);
}
}
}
int solution(int n, vector<int> weak, vector<int> dist) {
int answer = 10;
sort(dist.begin(), dist.end()); //거리 벡터 정렬
check(n, weak, dist, 0, answer); //확인 함수 호출
if (answer == 10) //답을 찾지 못한 경우
answer = -1;
return answer;
}결과
1) 가장 초기 코드의 결과
2) 제한을 적용한 최종 코드의 결과
