[알고리즘][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 인 경우를 살펴보자.
- 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 |
(꺼진 가로등은 빨간색으로 표시)
- 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->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 |
- 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 |
- 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문 : 오른쪽에 켜져있는 가로등이 남아있다면, 오른쪽으로 이동하여 끈다. 그 다음은 위와 동일하다.
- 이렇게 왼쪽과 오른쪽으로 갔을 때의 소비량을 구한 후, 더 작은 방향을 택한다.
- 재귀함수의 동작과정
재귀함수의 동작과정이 잘 이해되지 않아 모두 그려보았다.
💥 발전하자
- 추가로 공부해야 할 내용
- 재귀함수의 동작과정이 확 와닿지 않았다.
- 지금까지의 DP문제는 단순히 dp[i-1]을 활용해서 dp[i]를 구하는 문제가 대부분이었다. 하지만 이번 문제는 풀면서도 이게 DP를 활용하는 것인지 의문이 들고 헷갈렸다.
📌 참고하자
나의 코드(Github)
이해에 도움을 주신 고수님의 코드
Author And Source
이 문제에 관하여([알고리즘][BOJ]2315_가로등 끄기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@choiyhking/알고리즘BOJ2315가로등-끄기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)