[C++] 백준/BOJ - 1823 : 수확

문제 이해 단계

https://www.acmicpc.net/problem/1823

1823번: 수확

일렬로 나열되어 있는 정수가 1 ~ N까지 존재한다.
이 숫자들을 얻기 위해서는 양끝부터 얻어야 한다.

숫자를 얻었을 때 이익은 다음과 같다.
이익 = 숫자*(고른 순서)

해당 조건과 같을 때 얻을 수 있는 가장 최대의 이익을 구하는 문제

 

---

문제 접근 단계

벼의 개수는 최대 2,000개까지,
그리고 정수는 최대 1,000까지 가능하다.

일단 정수를 양쪽 끝에서부터 얻을 수 있기 때문에
왼쪽과 오른쪽을 분리해서 생각하긴 해야 할 것 같다.

처음에는 투포인터를 생각했는데
1 10 1 1 7 8 9
같은 경우는 투포인터로 양 끝 값부터 살펴보기 어렵다.

그래서 좀 다른 방식을 물색해봐야 했다.

왼쪽 끝에서부터 오른쪽으로 올라오고,
오른쪽 끝에서부터 왼쪽으로 올라온다.

이를 정수 범위로 나누고, 이 범위를 배열로 나타내보면?

예를 들어 arr [3][6]는 왼쪽 끝에서부터 3번째 인덱스까지 올라오고,
오른쪽 끝에서 6번째 인덱스까지 온 것이다.

여기까지 생각하니 DP가 생각나서
이 문제에 DP가 적용되는지 파악해 보았다.

예제케이스 1 3 1 5 2에서 arr [1][5]
즉, 왼쪽에서 1, 오른쪽에서 2를 수확할 때를 보자.

최댓값은 당연히 3이다.  

arr [1][4] 일 때 arr [1][5] 값이 변할까? 당연히 변하지 않는다.
5를 수확할 수 있든 말든 arr [1][5]에선 상관없기 때문이다.

즉, 한번 정해진 값은 고정적이다. DP의 조건이 성립된다.

---

DP 로직 세우기

해당 문제를 DP로 풀려면 점화식을 세워야 한다.
그러기 위해 DP배열을 만들어야 하는데,

왼쪽과 오른쪽 두 개의 범위가 존재하기 때문에 2차원 배열로 만든다.

위에서 세웠던 배열 가정대로

dp [left][right]
= left까지 수확하였고, right까지 수확하였을 때 최대 이익으로 하였다.

이제 최댓값을 구해야 하는데 이는 그림으로 한번 살펴보자

DP[L][R]이 존재한다고 가정

DP [L][R]이 존재하고, 이런 식으로 둘의 포인트를 나타내본다.

이제 여기서 최댓값을 찾기 위해 옮길 수 있는 다음 이동은?

당연히 L 또는 R을 옮기는 것 둘 중 하나일 것이다.
L을 옮긴다면 +1일 것이고, R을 옮긴다면 -1일 것이다.

이 둘 중 어느 게 더 큰 이익일지는 끝까지 다 가봐야 안다.
그렇기 때문에 재귀함수를 통해 끝까지 다 호출해 봐야 아는 것이다.

끝까지 다 호출해 보고 그 값들을 dp배열에 다 기억해 둔다.
결론적으로 점화식은 이렇게 된다.

dp [Left][Right] =
MAX(DP(Left+1, Right, count+1)+v [left]*count ,
DP(Left, Right-1, count+1) + v [right]*count)

뒤에 v [Left]*count나 v [right]*count는
수확한 이후 인덱스를 옮겨줘야 하기 때문이다.

이 점화식을 토대로 코드를 구현하면 된다.

 

---

문제 구현 단계

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int map[2001] = {0,};
int d[2001][2001] = {0,};

int dp(int left, int right, int count){
    if(left > right) return 0; // 왼쪽 값이 오른쪽보다 큰건 존재안함
    if(d[left][right]) return d[left][right]; // 이미 계산된 거면 그 값 반환

    // 점화식
    int val = max(dp(left+1,right,count+1)+ map[left]*count,
                dp(left,right-1,count+1)+ map[right]*count);

    return d[left][right] = val;
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    cin >> N;
    for(int i = 1; i <= N; i++) cin >> map[i];

    cout << dp(1,N,1);
}

DP이기 때문에 역시 코드는 간단하다.

설명할 것도 딱히 없고 left > right 일 때, 0을 반환하는 것만 유의하면 된다.

 

---

시행착오

투포인터로 풀다가 반례를 너무 뒤늦게 알았다.

나는 저 DP 범위를 반대로 생각해서 안쪽 범위로 만들어서
DP 식을 만들려고 하다 보니 도저히 DP식이 안 나왔다. 

DP는 역시 어려워..

https://toss.me/howudong

howudong님에게 보내주세요