BOJ_2315

💡 생각하자

Dynamic Programming(동적 계획법)의 개발절차
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기

주어진 예시 상황에 대해서 생각해보자.

가로등 번호	1	2	3	4	5	6
위치	3	11	12	13	15	17
소비량	2	10	18	19	15	19

마징가는 5번 가로등에서 출발한다.
다음으로는 4번 또는 6번으로 갈 수 있다.

4번으로 간 경우를 생각해보자.
여기서도 역시 3번 또는 6번으로 갈 수 있다.

그렇다면 예를 들어 5->4->3->2->1->6 인 경우를 살펴보자.

1. 5->4 : 2초 => 2⨯2 + 10⨯2 + 18⨯2 + 19⨯2 + 19⨯2 = 136

가로등 번호	1	2	3	4	5	6
위치	3	11	12	13	15	17
소비량	2	10	18	19	15	19

(꺼진 가로등은 빨간색으로 표시)

2. 4->3 : 1초 => 2⨯1 + 10⨯1 + 18⨯1 + 19⨯1 = 49

가로등 번호	1	2	3	4	5	6
위치	3	11	12	13	15	17
소비량	2	10	18	19	15	19

3. 3->2 : 1초 => 2⨯1 + 10⨯1 + 19⨯1 = 31

가로등 번호	1	2	3	4	5	6
위치	3	11	12	13	15	17
소비량	2	10	18	19	15	19

4. 2->1 : 8초 => 2⨯8 + 19⨯8 = 168

가로등 번호	1	2	3	4	5	6
위치	3	11	12	13	15	17
소비량	2	10	18	19	15	19

5. 1->6 : 14초 => 19⨯14 = 266

가로등 번호	1	2	3	4	5	6
위치	3	11	12	13	15	17
소비량	2	10	18	19	15	19

결과적으로 136+49+31+168+266 = 650만큼의 전력소비가 발생했다.

이렇게 모든 경우의 결과값을 구하여 비교하는 것은 매우 비효율적이므로, 매 선택의 기로에서(왼쪽/오른쪽) 최솟값을 택한다.

i부터 j까지의 모든 가로등이 꺼져있다면, 그 순간 마징가의 위치는 i이거나 j라는 사실은 확실하다.

재귀 관계식
dp[left][right][where] : left부터 right까지의 모든 가로등이 꺼진 순간 현재 위치가 where(0->left/1->right)일 때, 지금까지 소비된 전력량

case 1) left - 1 >= 1
result1 = dp[left-1][right][0] + (left에서 left-1까지 걸리는 시간)⨯(켜져있는 가로등들의 전력소비량의 총 합)

case 2) right + 1 <= n
result2 = dp[left][right-1][1] + (right에서 right+1까지 걸리는 시간)⨯(켜져있는 가로등들의 전력소비량의 총 합)

dp[i][j][where] = minimum(result1, result2)

💻 구현하자

• 초기 호출문

for (int i = 1;i <= n;i++) {
	scanf("%d %d", &location[i], &value[i]);
	c_sum[i] = c_sum[i - 1] + value[i];
}  
    
// init
for (int i = 0;i <= 1000;i++) {
	for (int j = 0;j <= 1000;j++) {
		for (int k = 0;k < 2;k++) {
			dp[i][j][k] = -1;
		}
	}
}

int res = calMinSum(m, m, 0);
printf("%d", res);

- 가로등의 위치와 전력소비량을 입력받을 때, 전력소비량의 '누적 합'을 구해준다.(계산의 편의를 위해)

• 전력의 최솟값을 구하는 함수

int calMinSum(int left, int right, int where) {
	if (left == 1 && right == n) { // finished(no more consumption = all lights are off)
		return 0;
	} 

	if (dp[left][right][where] != -1) {
		return dp[left][right][where];
	}

	int res = MAX;
	int now = where ? right : left;
	
	// choose the next path with the smallest cost!!(left or right)
	if (left - 1 >= 1) { // go left until #1 light(leftmost)
		res = calMinSum(left - 1, right, 0) + (location[now] - location[left - 1]) * (c_sum[n] - c_sum[right] + c_sum[left - 1]);
		// calMinSum(left - 1, right, 0) + all costs of lights still turned on when going from left to left-1
	}
	if (right + 1 <= n) { // go right until #n light(rightmost)
		res = min(res, calMinSum(left, right + 1, 1) + (location[right + 1] - location[now]) * (c_sum[n] - c_sum[right] + c_sum[left - 1]));
		// min(cost when going left, cost when going right) 
	}

	dp[left][right][where] = res;

	return res;
}

- left와 right가 각각 양쪽 끝에 도달하면 모든 가로등이 꺼진 상태를 의미하므로 0을 리턴한다.
- 이미 구해진 값이 있으면 그 값을 사용한다.
- 현재 마징가의 위치는 where값이 0이면 left, 1이면 right임을 의미한다.

- 첫번째 if문 : 왼쪽에 켜져있는 가로등이 남아있다면, 왼쪽으로 이동하여 끈다. 이동하는 시간동안 나머지 켜져있는 모든 가로등이 소비하는 전력량을 구해 더해준다.
- 두번째 if문 : 오른쪽에 켜져있는 가로등이 남아있다면, 오른쪽으로 이동하여 끈다. 그 다음은 위와 동일하다.

- 이렇게 왼쪽과 오른쪽으로 갔을 때의 소비량을 구한 후, 더 작은 방향을 택한다.

• 재귀함수의 동작과정
  재귀함수의 동작과정이 잘 이해되지 않아 모두 그려보았다.
  

💥 발전하자

• 추가로 공부해야 할 내용

1. 재귀함수의 동작과정이 확 와닿지 않았다.
2. 지금까지의 DP문제는 단순히 dp[i-1]을 활용해서 dp[i]를 구하는 문제가 대부분이었다. 하지만 이번 문제는 풀면서도 이게 DP를 활용하는 것인지 의문이 들고 헷갈렸다.

📌 참고하자

나의 코드(Github)
이해에 도움을 주신 고수님의 코드