[코드트리] 2차원 최대 증가 수열 C++

문제

https://www.codetree.ai/missions/2/problems/longest-increasing-sequence-2d?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획 세우기

칸을 선택하고, (0,0)부터 (i, j)까지 돌면서 dp를 갱신해야 한다. for문을 4개 써야 한다는 걸 떠올리는 게 중요한 거 같다?

풀이

#include <iostream>

using namespace std;
int n, m;
int arr[51][51];
int dp[51][51];

void FillDP(int x, int y){
     for(int i=0; i<x; ++i){
        for(int j=0; j<y; ++j){
            if(arr[x][y]>arr[0][0] && arr[i][j]<arr[x][y]){
                dp[x][y]=max(dp[x][y], dp[i][j]+1);
            }
        }
    }
}

int main() {
    // input
    cin >> n >> m;
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            cin >> arr[i][j];
        }
    }
    
    // solution
    dp[0][0]=1;
    for(int i=1; i<n; ++i){
        for(int j=1; j<m; ++j){
            FillDP(i, j);
        }
    }

    // output
    int answer =0;
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            answer=max(answer, dp[i][j]);
        }
    }
    cout << answer << '\n';
    return 0;
}