[Programmers] 정수 삼각형

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

전형적인 DP 문제다.

왜 이문제가 level 3인지는 모르겠으나..

 

def solution(triangle):
    answer = 0
    dp = [[0]*len(triangle) for _ in range(len(triangle))]
    
    dp[0][0] = triangle[0][0]
    for i in range(1, len(triangle)):
        triangle[i][0] += triangle[i-1][0]
        triangle[i][len(triangle[i])-1] += triangle[i-1][len(triangle[i-1])-1] 
    for i in range(2, len(triangle)):
        for j in range(1, len(triangle[i])-1):
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
    return max(triangle[len(triangle)-1])

 

아 파이썬에서 max 함수나 min 함수는 느리다고 합니다!!

왜 느리냐면 max(a,i)를 해서 새로운 값을 만들고 다시 a에 넣는다나..

그리고 for i in range(0,10): 이 구문도 range(0,10)라는 자료형을 만들어서 여기서 돌아가느라 .. 느리대요

하지만 while True로 계속 if문 비교하는거보단 빠름 ㅋㅋ

import time
start = time.time()

a = 0
for i in range(10000000):
    if a<i:
        a = i

print(time.time()-start)

위 코드는 시간이 0.4380989074707031

 

import time
start = time.time()

a = 0
for i in range(10000000):
	a = max(a,i)

print(time.time()-start)

위 코드는 1.0912463665008545

따라서 귀찮더라도.. 위의 코드를 사용하는것이!!