[PCCP] Lv3: 정수 삼각형(43105) 해설

문제

- 문제 링크: 정수 삼각형

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: 삼각형의 높이

- N*N 2차원 dp 테이블을 초기화할 때의 시간 복잡도는 O(N^2)

-dp 테이블을 채우는 동작 또한 O(N^2)이므로 최종 시간 복잡도는 O(N^2)

#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int n = triangle.size();
    vector<vector<int>> dp(n, vector<int>(n, 0)); // dp 테이블 초기화
    
    // dp 테이블의 맨 아래쪽 라인 초기화
    for (int i = 0; i < n; ++i) {
        dp[n - 1][i] = triangle[n - 1][i];
    }
    
    // 아래쪽 라인부터 올라가면서 dp 테이블 채우기
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
        }
    }
    return dp[0][0]; // 꼭대기에서의 최댓값 반환
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: 삼각형의 높이

- N*N 2차원 dp 테이블 초기화할 떄 시간 복잡도: O(N^2)

- dp 테이블을 채우는 동작: O(N^2)

- 최종 시간 복잡도: O(N^2)

class Solution {
    public int solution(int[][] triangle) {
        int n = triangle.length;
        int[][] dp = new int[n][n]; // dp 배열 초기화
        
        // dp 배열의 맨 아래쪽 라인 초기화
        for (int i = 0; i < n; ++i) {
            dp[n - 1][i] = triangle[n - 1][i];
        }
        
        // 아래쪽 라인부터 올라가면서 dp 배열 채우기
        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }
        return dp[0][0]; // 꼭대기에서의 최댓값 반환
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 삼각형의 높이

- N*N 2차원 dp 테이블 초기화: O(N^2)

- dp 테이블을 채우는 동작: O(N^2)

- 최종 시간 복잡도: O(N^2)

def solution(triangle):
    n = len(triangle)
    dp = [[0] * n for _ in range(n)] # dp 테이블 초기화
    
    # dp 테이블의 맨 아래쪽 라인 초기화
    for i in range(n):
        dp[n - 1][i] = triangle[n - 1][i]
        
    # 아래쪽 라인부터 올라가면 dp 테이블 채우기
    for i in range(n - 2, -1, -1):
        for j in range(i + 1):
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
            
    return dp[0][0] # 꼭대기에서의 최댓값 반환

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: 삼각형의 높이

- N*N 크기의 2차원 dp 테이블 초기화: O(N^2)

- dp 테이블을 채우는 동작: O(N^2)

- 최종 시간 복잡도: O(N^2)

function solution(triangle) {
    const n = triangle.length;
    const dp = Array.from(Array(n), () => Array(n).fill(0)); // dp 테이블 초기화
    
    // dp 테이블의 맨 아래쪽 라인 초기화
    for (let i = 0; i < n; ++i) {
        dp[n - 1][i] = triangle[n - 1][i];
    }
    
    // 아래쪽 라인부터 올라가면서 dp 테이블 채우기
    for (let i = n - 2; i >= 0; --i) {
        for (let j = 0; j <= i; ++j) {
            dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
        }
    }
    
    return dp[0][0]; // 꼭대기에서의 최댓값 반환
}

solution 2)

import

solution 3)

import