배열 원소간 모든 차이값을 주어진 값 이하로 맞추는 최소 변환 수

차이값을 주어진 값 이하로 맞추면서, 원래 배열에서 최소 한도로 움직이도록 해야 한다. 그 바꾼 값을 반환하자.

ex )

[1,4,2,3]

target = 1;

>> 

ans :

[2,3,2,3]

바꾼 양 : 2  >>> ans = 2

** 솔직히 이 문제는 "최적 값을 구하시오" 그리고 "숫자 상한이 100이다" 에서 - 아 이 문제는 DP구나 가 바로 떠올라서 완전 탐색으로 넘어갈 생각을 했어야 한다. 뭐 그리디 한두번은 해볼 수 있었겠지만 안정적으로 DP를 해놓고 찾았을꺼다. **

솔루션 : 

그리디 솔루션 :

한쪽 끝에서부터 생각해 보자. 한도 내로 맞추기 위해서 1을 움직일까 4를 움직일까?

아님 중간으로 맞출까?

일단 움직이는 총량은 같다. 어찌됬든, 차이를 그렇게 만들어야 하기 때문.

그럼 그 다음 값이 무엇이냐에 따라 결정되겠다.

만약 1,4,5 였으면 3,4,5 로 바꾸는 것이 최선이고(4를 내리면 5를 내려야 한다. 5 뒤에 어떤 값이 있다고 할때)

1 4 5 3

3 4 5 4

1 4 100 1 1 1 1 1 1

최적화는 방법이 조금 복잡할 수 있어서 다른 방법이 있을까?

아니면 꼬리치는 용같은 방식으로 그냥 각자의 최소를 가져다 댄다.

1 4 2 3

3 4 2 3

2 3 2 3 >> 그리고 차이값을 계산한다.

1 4 100 1 1 1 1 1 1

3 4 100

98 99 100 1

//

아니면 전체의 평균에서 출발해 볼까? 거시적으로 보는거야.

1 4 5 3 >> 평균 13/4 = 3.xxx

3 3 3 3 >> 그리고 여기에서 각자 더 작은애는 작은쪽으로 큰애는 큰쪽으로 암튼 전후로 최소 움직임을 찾아보는거야.

별로 아닌듯.. 불연속적인 차이값들 구성이 가능해서

// 아니면 극단적인 값부터 배치 ? .. 노

DP 방법이 있는 것 같다.

curr 뒤에의 값을 맞춘 최솟값을 m 이라고 하면

지금 값을 뒤에의 값들과 맞추는 비용 k와

뒤에의 값들을 평행이동 해서 앞의 값과 맞추는 비용 l 중 작은 경우로 결정한다.

평행이동이 아니라, 왼쪽 끝을 움직이고 나머지가 조건에 맞도록 하는 비용이 되겠다..

리턴받는 값을 제일 왼쪽의 숫자 + 횟수로 하고.

그러면 평행이동을 하는 것이 그 이후의 최솟값임이 보장되나?

1 4 2 3

2 3, 0

4

" 지금 이 점을 이 값으로 fix 하고 다음을 정했을 때의 최솟값 "

curr 부터 끝까지 배치하는 최소 수, curr의 값을 반환받아 보자.

3 99 100 99

3을 상방 배치하는 경우 95

나머지를 하방 배치하는 경우 매우 큼

>>

98 99 100 99, 값 : 95+그거

------------------

그리디 아님 DP 문제다!! 한번 더 고민해 보자.

겁나 어렵네 ;;

역시 iterative DP 문제였음.. 내 약한 부분..

아 근데 값의 상한이 100이라는 점을 안 썼네;;

값의 상한이 100이라는 점은 "카운팅 소트" 를 한다 라는 생각도 있겠지만

"값에 대해 DP를 돌려버린다" 도 가능하다 ㅋㅋㅋ

일단 창의적인 솔루션도 좋은데 DP를 간단하게 먼저 생각해 보는게 좋겠다. DP는 시스테매틱하니까..!!

----------------

내 약한 부분이 아니라 접근 방법이 전문적이지 못했다.

1. 바로 보이는 접근(답을 아는 경우나 정말 간단히 답이 보이는 경우)

2. 나이브 솔루션이라도 하나 굳힌다. 정말 개노가다 방법이어도 좋다. 여기서 출발한다.

3. 성질을 연구해서 DP로 줄이거나 그리디 솔루션을 찾는다.

-----------------

그리디는 답이 없는게 확실해졌고 결국 DP 문제였음.. 최적화기도 하니까 최적화 보이면 아 DP겠구나.. 생각해야겠다

값의 상한이 100이기 때문에, MAX 를 DP에 넣어서 풀어도 충분하다.

dp >> curr을 j로 바꿨을때 최솟값

값의 상한이 100이기 때문에 그냥 때려박아서 풀어도 된다.

즉,

1 4 2 3 이면 1을 0에서 100까지 전부 해버리는거다.

아, 결국 이런 완전탐색이었구나!!

헐........... 값의 범위가 있어버리면 이거를 완전탐색 해버리는거다. 그리고 DP를 하는거지

깨닳음

int findmin(vector<vector<int>> & cache, vector<int> & data, int K, int curr, int prev){

if(curr==data.size()) return 0;

if(cache[prev][curr]!=-1) return cache[prev][curr];

int ret = INT_MAX;

for(int i = 0 ; i <= 100 ; i++){

if(abs(i-prev)<=K){

ret = min(ret,findmin(data,curr+1,i)+abs(i-prev));

}

}

cache[prev][curr] = ret;

return ret;

}

결론 : DP는 결국에 고상한 척 하는 노가다다. 그것도 아주 많은 갈래로 쪼개지는 노가다를 단지 그 "쪼개짐의 값의 범위" 로 상한을 정해놓았을  뿐..

아 진짜 그러네 결국에 완전탐색인데 완전탐색중에 "쪼개짐의 값의 범위" 가 제약되어 있는 경우에 그 쪼개짐의 값의 범위에 대해 상한이 정해지는 것 뿐이네. 결국에는 O(5^N) 이딴 알고리즘인데.

만약 인자가 두개 뿐이어도 그 인자 하나가 1억의 범위를 가져버리면 DP고 뭐고(가능은 하다..) 심지어 안 겹치면 정말..!!

DP의 성질

* 겹쳐야 빨라진다.

* 범위가 좁아야 상한의 의미가 있다

암튼 저거의 시간 복잡도는 O(MAX^2 * N) 이다 ( 각 재귀함수에서 MAX 회 수행시간 )

이게 1억이었어봐 ..

숫자의 범위는 카운팅 소트 뿐이 아니라 DP에서도 매우매우매우 !!! 중요하다 !!