백준 1932번, 정수 삼각형(C, C++)

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

1932번: 정수 삼각형

 

 

잘못 생각한 문제!!

#include<iostream>
#include<algorithm>

using namespace std;
int n;
int map[500][500];
int j = 0;
int MAX = 1000000000;
bool visited[100][100];
int dx[2] = {0, 1};
int solution = 0;

void dfs(int y, int x, int depth, int sum){
    
    if(depth == n){
       solution = max(sum, solution);
    }

    for(int i = 0; i < 2; i++){
            int ny = y+1;           //오른쪽과 왼쪽으로 가는 경우
            int nx = x + dx[i];

        if(ny < 0 || ny>=n || nx < 0 || nx>=n){
            continue;
        }
        dfs(ny, nx, depth+1, sum + map[ny][nx]);
    }
}

int main(){

    cin >> n;


    for(int i = 0; i < n; i++){
        for(int j = 0;  j <= i; j++){
            cin >> map[i][j];
        }
    }
    dfs(0, 0, 1, map[0][0]);

    cout<<solution<<endl;
 
}

 

처음에 DFS로 풀어야겠다고 생각했다.

그러나 결과는 시간초과

시간 제한 2초라는 것을 간과하고 있었다.

문제에서 삼각형의 크기가 최대 500까지 설정되어 있는데,

여기서 1초당 수행횟수 1억번을 넘으면 시간제한 초과 가능성이 있다.

DFS식을 사용하면

대략 for문을 크기만큼 돌린다고 쳤을때 2억번을 넘는다.

따라서 시간 초과가 날 수 밖에 없음.

 

그래서 다이나믹 프로그래밍(DP)를 사용하기로 했다.

 

#include<iostream>
#include<algorithm>

using namespace std;

int map[502][502] = {0};
int main(){
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <=i; j++){
            cin>>map[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            map[i][j] += max(map[i-1][j-1], map[i-1][j]);
        }
    }

    //마지막 값 비교
    int max = 0;
    for(int i = 1; i <= n; i++){
        if(max < map[n][i]){
            max = map[n][i];
        } 
    }
    cout << max;

    return 0;
 
}