[Algorithm] Baekjoon 1736번 : 쓰레기 치우기

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

1736번: 쓰레기 치우기

int dp[101][101];
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, m;
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> dp[i][j];
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = m; j >= 1; --j)
        {
            dp[i][j] = max({ dp[i][j + 1], dp[i - 1][j], dp[i][j] + dp[i - 1][j + 1] });
        }
    }
 
    cout << dp[n][1];
}

이번 문제는 스스로 풀수는 없었고,

http://codersbrunch.blogspot.com/2017/07/1736.html

1736번: 쓰레기 치우기

이 분의 풀이를 보고 푼것이고(동일한 코드), 해설은 나름 생각한대로 쓴 것이다.

 

DP로 깔끔하게 푼 풀이인데, 다른사람들 풀이보면 이렇게 DP로 푼 풀이는 거의 존재하지 않는다.

사실 뭘로 풀든 풀리기만 하면 상관없지만, DP에 좀 익숙해지고자 DP코드를 풀이해보려 한다.

 

먼저 탐색은 행방향의 경우 그대로이지만 열방향은 반대로, 즉 끝에서부터 체크한다.

이유로는 정방향으로 탐색하려할 경우 쓰레기를 발견했을 때, 이대로 행이동하면서 체크할지 열이동을 해서 더체크해야할 지 알 수 없기 때문이다. 열을 역방향으로 탐색하면 끝에서부터 쓰레기의 유무를 반영해서 기록하기 때문에 역방향으로 체크한다.

 

그다음 DP[i][j]에 기록하는것을 보면 해당칸의 위([i-1][j]),   오른쪽([i][j+1]),   현재값([i][j]) + 오른쪽위대각선([i-1][j+1])

의 값들 중, 가장 큰값을 대입한다는 것을 알 수 있다.

 

선택지에 위,오른쪽이 있는 이유는 값의 기록을 우측 상단에서부터 시작했기 때문이다.(열을 역순으로 기록했으니까)

우측상단에서부터 각 칸들에 필요한 로봇의 수를 기록하면서 왔기 때문에 그 값들을 그대로 계승할 수도 있기 때문이다.

 

그리고 선택지에 '현재값 + 오른쪽위대각선'이 있는 이유는, 실질적으로 +1씩 카운팅해주는 선택지이다.

예를들어 3,3을 훑은 로봇이 2,2를 훑을 수 있을 수 없다. 문제에서의 로봇은 오른쪽,아래로만 움직일 수 있기 때문이다.

그렇기 때문에 2,2지점에서 3,3지점을 살펴본 후, 해당값을 계승하려면 +1을 해줄수밖에 없다. 즉, 새로운 로봇을 쓸 수 밖에 없다.

 

일련의 업데이트들을 마친 후, 1,m의 dp값을 출력해주면 된다.

n,m이 아닌이유는, 말했듯이 열을 역으로 탐색했기 때문이다.

나름 저 코드를 보고 해석했는데, 아직 DP문제경험이 너무 부족해서 제대로 했는지는 모르겠다..

 

DP문제가 확실히 해당유형으로 생각을 잘해야하고, 그래서 어려운 경향이 있긴한데 사실 다른 유형의 풀이랑 비교했을 때 효율이 정말 많이 차이나긴한다. 

이 문제같은경우는 N,M값이 작아서 어떤 풀이로하든 어지간하면 통과하겠지만 N,M값이 정말 크다면 어떻게될까??

그런거 생각하면 DP문제를 또 안풀어볼 수가 없다.