[백준 1106] DP 동적프로그래밍

동적 프로그래밍(Dynamic programming)이란 과거에 사용한 값을 중복해서 사용하는 경우에서 사용할 알고리즘을 말한다. 대표적으로 배낭 문제, 피보나치 수열이 있다. 
이전에 구해놓은 값을 재사용하기 때문에 재귀함수를 이용해야 한다. 

재귀함수를 naive하게 사용하게 되면 시간, 공간복잡도가 폭발적으로 증가한다.
부분 문제에 대한 값을 미리 계산해놓고 한 번에 이용하는 것이 시공간 관점에서 효율적이다.
 

따라서 Memoization(메모이제이션)을 활용한다.

같은 문제의 풀이를 재활용하는 방식인데, 재귀의 방법이 있다. 부분 문제에 대한 경우의 수를 모두 구할 건데, 이 때 재귀를 사용한다. 부분 문제를 넣고(1), 빼고(0) 에 대한 경우의 수를 구하는 것이다.

dp의 memoization은 하향식으로 메인에서 시작해 낮은 단계를 만들어가기 때문에 하향식이다.
 
자자 ㅡ 코드를 보자

int fib[MAX] = {0};

int fibonacci (int n ) {
	if (n <=1 ) return n;
    //fib[n]이 존재하지 않는 경우에 위에서부터 만들어가면서 구하므로 하향식이다.
    if ( fib[n] ) return fib[n];
    else return fib[n] = fibonacci(n-1) + fibonacci(n-2);
    }

 

상향식 풀이는 Tabulation이라고 한다.
상향식 풀이는 f[0] = 0, f[1] = 1로 지정해놓고 이를 조합해서 f[n]을 구하는 방법이다.

---

 

 
이 문제는 적어도 몇 명은 만족하는 최소 비용을 구하는 문제다. 
만약 도시 B는 3의 비용으로 1명을 늘리고 도시 A가 1의 비용으로 3명을 늘릴 수 있다면 
2명을 채울 때 B는 ($6, 2명) A는 ($1, 3명)을 가진다. 즉, C와 동일한 고객 수가 최소 비용이 아닐 수 있다.
따라서 고객수는 C보다 더 크게 잡는다.

특정 고객수에 형성되는 가격을 하나의 부분 문제로 가지고 이를 재활용한다. 그리고 요소를 넣었다, 뺐다(0, 1)로 경우의 수를 구하기 때문에 DP 문제다.    

dp의 i 인덱스를 cost로 두는 경우와 dp의 i를 people로 두는 경우, 두 가지의 풀이법을 찾았다. 

인덱스를 cost로 두는 경우가 훨씬 직관적이라고 느껴졌다. return이 훨씬 깔끔해진다. 

// 각 도시별 cost와 man을 vector에 pair로 넣은 상황
if (i - cost >= 0) {
	dp[i] = max(dp[i], dp[i-cost] + man);
    }
    
    /* 중략 */

for (int j = 1; j <= 100000; j++){
	if (dp[j] >= C) {
    	cout << j;
        break;
    }
}

https://littlesam95.tistory.com/entry/BOJGold-5-%EB%B0%B1%EC%A4%80-1106-%ED%98%B8%ED%85%94C

[BOJ/Gold 5] 백준 1106 호텔(C++)

 
하지만 이것은 와우코드.. 처음에 나는 dp[i]를 cost로 놓았고, dp[i] > dp[i - man] + cost 를 만족하는 경우에 dp[i]를 더 작은 cost로 업데이트하는 코드를 생각했다. 

dp 초기화할 때 애를 먹었다. dp[10000] 이렇게 대략하면 되는데 man+100으로 하고 싶어서  첫 for문에서 선언했더니 지역변수로 사라졌다...  미리 선언하고 인덱스 범위를 dp[man + 100]로 수정하려고 보니 그게 더 복잡해졌다. 만약 수정하고 싶다면 인덱스에 문자 변수를 넣고 변수를 고쳐야 한다. 
아직 어렵다 ㅠㅠ

이건 dp[i]의 값이 cost인 경우의 코드다. 매우 깔끔.. 최고..
https://leesh111112.tistory.com/434

[BOJ/백준][Gold5] 1106 : 호텔 (C++)