白駿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];
}
Reference
この問題について(白駿1932号:整数三角形), 我々は、より多くの情報をここで見つけました https://velog.io/@danbibibi/백준-1932번-정수-삼각형テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol