#include <bits/stdc++.h>
using namespace std;
int answer = 0, mmax = 0, kk = 0;
bool home[100001];
int hackerlandRadioTransmitters(vector<int> vec, int k)
{
kk = k;
memset(home, false, sizeof(home));
for (int i = 0; i < vec.size(); ++i)
{
home[vec[i]] = true;
mmax = max(mmax, vec[i]);
}
for (int i = 1; i <= mmax;)
{
if (home[i])
{
++answer;
int cnt = 0;
for (int s = 1; s <= kk; ++s)
{
if(i + s <= mmax && home[i + s])
cnt = max(cnt, s);
}
i += kk;
i += cnt;
}
++i;
}
return answer;
}
* 문제 풀이 과정
"최대한 많은 범위를 포함하도록 Transmitter 를 설치한다." 라는 개념을 이해한다.
한 가지 주의할점은 House 가 존재하는 곳에만 Transmitter 를 설치한다는 것이다.
따라서,
1. House 가 존재하는 곳을 찾는다.
2. 최대한 길게 범위를 만들어야함으로 다음 위치에 House 가 존재하는지 확인한다.
3. 답을 구한다.
* 해결 과정 문제점
제일 큰 문제점은 문제 이해를 잘못해서 House 가 존재하는 곳에만 설치해야한다는 사실을 알지 못했다.
그로 인해,
쉽게 구할 수 있는 방식에서 당연히 오답이 나왔다.
그래서 방식 자체를 바꾸려했고 의도치 않게 (?)
경우의 수로 접근해 DFS 방식을 거쳐 DP 방식까지 이리저리 고쳐가며 구현해봤다.
물론, 첫 문장에 말한 사실을 모른 상태에서 구현은 틀리겠지만
방식 자체도 문제가 있었다고 생각한다.
우선, DFS 는 모든 경우를 구해야하므로 시간 초과가 생긴다.
나는 이것을 해결하기 위해서 중복된 부분을 없애야 한다고 생각했고
DP 배열을 만들어 적용시키려고 했다.
하지만 이 문제에서 DP 의 의미가 없다.
DP 란 무엇인가 ??
간단하게 "부분문제 + 부분문제 = 현재문제" 이다.
즉,
현재의 상황이 다른 이전의 상황들이 합쳐진 상황이 된다는 말이다.
문제에 문제를 거듭할수록 겹치는 부분 문제를 메모리에 저장해 재활용하는 것을
'메모이제이션' 이라고도 한다. 이것이 DP 의 주요 성질이다.
이 문제에 대입해보면
1, 2, 3, 4 에서 굵게 칠해진 곳이 House 가 존재하는 곳, k = 1 이라 가정할 때,
배열 [4] 의 의미는 4까지의 Transmitter 가 최소로 쓰이는 최솟값이 되겠다.
최소값은 1 이 되겠다.
한 가지 예를 더 들어보자면,
1, 2, 3, 4 도 마찬가지로 최솟값은 1이 된다.
이 상황에서 5번째 위치의 배열 [5] 를 구한다고 하자. 만약 House 가 존재하면,
1번째 경우 : 1, 2, 3, 4, 5 -> 최솟값 : 2
2번째 경우 : 1, 2, 3, 4, 5 -> 최솟값 : 1
최솟값이 달라졌다.
결국, 경우마다 최솟값이 다르게 나오기 때문에
위 2가지의 경우를 나눌 수 있는 부분 문제로 만들어야하고 그것을 보통 Dp 배열로 구현한다.
또한,
배열 [5] 의 상황은 자신이 3에서 시작으로 하는 범위에 있는지 4에서 시작하는 범위에 있는지 알아야한다.
그렇다면 배열 [5] 의 상황은 무엇을 합친 문제인가??
판별하기가 어렵다.
해당 위치에 들어섰을 때, 그 때 상황에서 알아야할 정보가 너무 많고 부분 문제를 나누기가 힘들다.
왜냐하면, 이것은 중복되는 부분 문제가 아니라 "독립적인 경우의 수" 이기 때문이다.
결론적으로, 문제 조건을 알지 못해 답은 틀렸고
Dp 를 적용한다면 독립적인 문제를 억지로 부분 문제로 만드는 코드 구현으로 절대 맞출 수 없다.
또한 재대로 구현했다고 해도 어차피 같은 경우의 수를 구하는 것이기에 DFS 와 별반 차이가 없다.
( Dp 에 사용되는 배열로 인해 메모리만 더 커진 것일 뿐. )
스스로 DP 에 대해서 재대로 이해하지 못하고 무작정 쓰려고 한 것처럼 보인다.
이 문제를 통해 배운 사실을 기록하고 싶었다. 그로 인해, 글이 조금 길어졌다.
최대한 줄이려 노력했는데 글에 나오는 DP 는 워낙 이해하기 힘들고 설명도 많이 필요해 그런 것 같다.
그래도 의도치 않게 Dynamic Programming 개념에 대해 스스로 정리하는 글도 되었다.
