백준 1932번: 정수 삼각형

문제

문제 바로가기> 백준 1932번: 정수 삼각형

풀이

아래부터 쌓아 올라가는 방식으로 합이 최대가 되는 경로를 구했다.

import sys
n = int(input())
tri = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
for i in range(n-2, -1, -1):
    for j in range(i+1):
        tri[i][j]+=max(tri[i+1][j] ,tri[i+1][j+1])
print(tri[0][0])

코드 개선

아래와 같이 함수 형태로 작성하니 시간이 더 단축되었다.

def solution():
    import sys
    n = int(sys.stdin.readline())
    tri = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
    for i in range(n-2, -1, -1):
        for j in range(i+1):
            tri[i][j]+=max(tri[i+1][j] ,tri[i+1][j+1])
    print(tri[0][0])
solution()

c++을 이용한 풀이

#include<iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n; cin>>n;
    int tri[n+1][n+1]={};
    for(int i=0; i<n; i++){
        for(int j=0; j<i+1; j++){
            cin>>tri[i][j];
        }
    }
    for(int i=n-2; -1<i; i--){
        for(int j=0; j<i+1; j++){
            tri[i][j] = tri[i][j]+max(tri[i+1][j], tri[i+1][j+1]);
        }
    }
    cout << tri[0][0];
}