외벽 점검

https://school.programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스

 

내 아이디어

 

이 문제를 풀면서 가장 먼저 완전탐색을 고려했다.

내 계산에서 완전 탐색은 시간초과였다.

8가지 dist를 15가지의 weak point에 배치하는 것은 15 * 14 * ... * 8 > 2억 이었기 때문이다.

 

하지만, 이건 틀렸다.

 

정답 아이디어

 

내 아이디어가 틀린 이유는, 순서가 있는 8개의 dist를 띄엄띄엄 배치하는 것까지 고려했기 때문이다.

(나만 이런 생각을 했나.. 하고 다른 사람의 풀이를 보니 나같은 사람이 더 있다는 것에 안도했다.)

 

그림과 같이, 친구 배치를 띄엄띄엄 하면 어쩌피 빈 곳에 친구를 배정하는 일이 없다.

즉, dist를 결정했으면 "순서대로 붙여서" 배치해야 한다.

 

이런 식으로 말이다. (예시 그림이 충족시키지 못하는 것은 마찬가지임)

 

1) 바로 위의 예시처럼 dist를 전부 사용했는데 모든 weak point를 덮지 못하는 경우가 있을 것이고,

2) dist를 다 쓰지도 않았는데 조건을 충족시킬 수도 있다.

 

1)의 경우 그냥 실패다. -1을 return해야 한다.

2)의 경우 현재 최소 answer과 비교해서 더 적은 수의 dist를 썼다면 갱신해주면 된다.

 

그럼 이렇게 했을 때의 시간복잡도는 얼마일까?

dist의 순열을 구하는 경우의 수 : 8!

dist의 첫 번째 요소의 starting point를 정하는 횟수 : 15

starting point를 정한 이후 친구 배치 : 8

= 8! * 15 * 8 < 5백만

O(5백만)이 된다.

 

코드

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
const int INF = 2100000000;

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = INF;
    int defaultWeakSize = weak.size();
    vector<int> tmpWeak;
    for (auto e: weak) tmpWeak.push_back(e + n);
    for (auto e: tmpWeak) weak.push_back(e);
    
    do {
        for (int i = 0; i < defaultWeakSize; i++) {
            int startingPoint = weak[i];
            int curEndPoint = startingPoint;
            
            for (int j = 0; j < dist.size(); j++) {
                int nextWeakPoint;
                for (int k = 0; k < weak.size(); k++) {
                    if (weak[k] > curEndPoint) {
                        nextWeakPoint = weak[k];
                        break;
                    }
                }
                if (nextWeakPoint >= startingPoint + n) {
                    answer = min(answer, j+1);
                    break;
                }
                curEndPoint = nextWeakPoint + dist[j];
                if (curEndPoint >= startingPoint + n) answer = min(answer, j+1);
            }
        }
        
    } while (next_permutation(dist.begin(), dist.end()));
    
    return answer == INF ? -1 : answer;
}