#12913 땅따먹기

https://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

 

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최댓값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

landanswer

[[1,2,3,5],[5,6,7,8],[4,3,2,1]]

16

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

---------------------------------

 

정말 오랜시간 고민했던 문제.

몇날며칠을 봐도 푸는 방법을 모르겠는데 이 문제를 풀지않고는 다른 문제를 풀고싶지 않아서 내내 붙잡고 있었다....(원래 코딩테스트 문제들은 빨리빨리 푸는게 정석이기 때문에 이렇게 하면 안된다)

 

처음에 푼 방식은

반복문으로 처음부터 끝 행까지 돌린다 -> 매 행마다 제일 큰 값을 구해서 더한다 -> return

이었다

근데.. 테스트만 통과하고 채점을 돌리니 다 틀리는 것이다!!(절규)

 

이게 무작정 max값으로 구하면 안되는게, 반례가 생각보다 많다.

예를들어

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 10 | 1 |

이라고 치자

그러면 (max값 && 앞에 행이랑 다른 행)만 구한다 치면 5->7->4 = 16 이 된다

그러나  5->6->10 = 21  이 경우가 더 크다

왜냐하면, 2번째값에서 최댓값인 7을 선택하게 되면, 3에서 다른 값들보다 차이가 많이 나는 10을 얻을 수 없기 때문이다.

그래서 2행에서 1을 손해보더라도 10을 얻기 위해서 6으로 가는 것이 맞다.

 

 

이 문제는 사실 Dynamic Programming으로 풀어야 한다.

 

https://youtu.be/vYquumk4nWw

종종 보는 도조 영상. 강의력이 좋다. 영어지만.....

Dynamic Programming이란,

우리나라 말로 '동적 계획'이라고 한다. 여기서 Programming이라는건 우리가 말하는 컴퓨터의 프로그래밍이 아니고, 티비에 나오는 '방송 프로그램' 정도의 뉘앙스이다. 

Dynamic Programming에서 가장 핵심적인 키워드는 Memoization. Memorization 아니다! 정확히 메모'아이'제이션(우리나라 사람들은 메모이제이션이라고 하더라). 이전에 구한 값을 굳이 다시 계산하지 말고, 저장해뒀다가 다시 쓰자는 거다. 그리고 배열을 이용하여 상향식으로 답을 구하는 Bottom-Up 방식이다.

 

 

 

알고리즘 공부해야하는데 공부해야하는데... 중얼대기만 했던 과거를 반성하며 이번에 전공책을 다시 펴서 공부했다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int> > land)
{
    int rear = land.size() -1;
    
    for( int i = 0 ; i < rear ; i++){
        //for( int j = 0 ; i < 4 ; i++)
        land[i+1][0] += max(land[i][1],max(land[i][2], land[i][3]));
        land[i+1][1] += max(land[i][0],max(land[i][2], land[i][3]));
        land[i+1][2] += max(land[i][0],max(land[i][1], land[i][3]));
        land[i+1][3] += max(land[i][0],max(land[i][1], land[i][2]));
    }
    
    return *max_element(land[rear].begin(), land[rear].end());
}

여기서 포인트는, 굳이 배열을 따로 만들지 않고 land vector을 그대로 활용한 것. DP는 한번 값 구하면 끝이고 다시 돌아갈 필요가 없기 때문에 그냥 최댓값 구하는 대로 덮어씌우면 된다.

그리고 겉보기에는 되게 하드코딩 한 것 처럼 보이는데, 이게 그냥 낫더라. 이전의 열과 겹치지 않도록 구현하는 게 간단치 않음.

아무튼 그렇게 해서, <algorithm> 헤더에 있는 max_element를 이용해서 최댓값을 반환하며 된다.