[#22][알고리즘] 땅따먹기 게임

프로그래머스 > 땅따먹기 게임

문제 링크(https://programmers.co.kr/learn/challenge_codes/154)

C++풀이

#include<iostream> #include <algorithm> using namespace std; int hopscotch(vector<vector<int> > v) {   int answer = 0;   int dp[1000][4] = {0};   //dp[0][0]~dp[0][4] 값 셋팅   for(int i = 0; i < 4; i++)       dp[0][i] = v[0][i];         for(int i = 1; i < v.size(); i++)       for(int j = 0; j < 4; j++)         for(int k = 0; k < 4; k++)           if(j != k) // 같은 열을 연속해서 밟을 수 없음             dp[i][j] = max(dp[i][j], v[i][j] + dp[i-1][k]);      //점수가 모두 더해진 마지막 행에서 최대 값 찾기        for(int i = 0 ; i < 4; i ++)       answer = max(answer, dp[v.size()-1][i]);   return answer; } int main() {     vector<vector<int> > test{{1,2,3,5},{5,6,7,8},{4,3,2,1}};  //아래는 테스트로 출력해 보기 위한 코드입니다.     cout << hopscotch(test); } Colored by Color Scripter

cs

• i=1, j=0일 때 

     dp[1][0] = max(dp[1][0], v[1][0]+dp[0][k])
     k=1 : dp[1][0] = max( 0, 5+2 ) = 7
     k=2 : dp[1][0] = max( 7, 5+3 ) = 8
     k=3 : dp[1][0] = max( 8, 5+5 ) = 10
     dp[1][0] = 10

• i=1, j=1일 때

     dp[1][1] = max(dp[1][1], v[1][1]+dp[0][k])
     k=0 : dp[1][1] = max( 0, 6+1 ) = 7
     k=2 : dp[1][1] = max( 7, 6+3 ) = 9
     k=3 : dp[1][1] = max( 9, 6+5) = 11
     dp[1][1] = 11

• i=1, j=2일 때

     dp[1][2] = max(dp[1][2], v[1][2]+dp[0][k])
     k=0 : dp[1][2] = max( 0, 7+1 ) = 8
     k=1 : dp[1][2] = max( 8, 7+2 ) = 9
     k=3 : dp[1][2] = max( 9, 7+5 ) = 12
     dp[1][2] = 12

• i=1, j=3일 때

     dp[1][3] = max(dp[1][3], v[1][3]+dp[0][k])
     k=0 : dp[1][3] = max( 0, 8+1 ) = 9
     k=1 : dp[1][3] = max( 9, 8+2 ) = 10
     k=2 : dp[1][3] = max( 10, 8+3 ) = 11
     dp[1][3] = 11

• i=2, j=0일 때

     dp[2][0] = max(dp[2][0], v[2][0]+dp[1][k])
     k=1 : dp[2][0] = max( 0, 4+11 ) = 15
     k=2 : dp[2][0] = max( 15, 4+12 ) = 16
     k=3 : dp[2][0] = max( 16, 4+11 ) = 16
     dp[2][0] = 16

• i=2, j=1일 때

     dp[2][1] = max(dp[2][1], v[2][1]+dp[1][k])
     k=0 : dp[2][1] = max( 0, 3+10 ) = 13
     k=2 : dp[2][1] = max( 13, 3+12 ) = 15
     k=3 : dp[2][1] = max( 15, 3+11 ) = 15
     dp[2][1] = 15

• i=2, j=2일 때

     dp[2][2] = max(dp[2][2], v[2][2]+dp[1][k])
     k=0 : dp[2][2] = max( 0, 2+10 ) =12
     k=1 : dp[2][2] = max( 12, 2+11) = 13
     k=3 : dp[2][2] = max( 13, 2+11) = 13
     dp[2][2] = 13

• i=2, j=3일 때

     dp[2][3] = max(dp[2][3], v[2][3]+dp[1][k])
     k=0 : dp[2][3] = max( 0, 1+10 ) = 11
     k=1 : dp[2][3] = max( 11, 1+11 ) = 12
     k=2 : dp[2][3] = max( 12, 1+12 ) = 13
     dp[2][3] = 13

=> dp[2][0], dp[2][1], dp[2][2], dp[2][3] 중 최대값 = 16