[ 프로그래머스 ] 정수 삼각형 파이썬python 풀이

 

 

//문제 요약

 

정수로 된 삼각형이 주어지면

 

아래로 이웃한 두 정수와 만 더해질 수 있다고 할때

 

가장 큰 합은 얼마인지 구하여라

 

 

 

//풀이

 

나는 이거 처음에 무조건 dfs 라고 생각했다.

 

그리고 완전 틀려먹고나서

 

그냥 그리디로 풀면 되는 문제라는걸 깨달았다.

 

코테를 준비하면서 점점 더 많이 느껴지는 것은

 

이 문제는 그리디다! DFS다! DP다! 이런게 처음에 배울땐 의미가 있지만

 

나중에 문제를 마주하면 크게 의미가 없다.

 

솔직히 그래프로 풀어서 정말 효율적인 문재들은 굉장히 소수의 문제이고

 

대부분의 경우에서 그리디 / 동적프로그래밍 으로 풀게 되는데

 

이것도 구분이 점점 모호하고..

 

그냥 자신만의 어떤 스타일이 굳어지면 더 이상 구분하는 것도 의미가 없어진다.

 

다른 사람들과 소통하고 공식적인 자리에서 꼭 써야하는 경우가 아니면 말이다.

 

아무튼 이번 풀이는 이렇다.

 

이렇게 화살표방향으로 계속 더해가면서 값을 누적시키고

 

화살표 2개가 만나는 지점은 더 큰 값으로 누적시켜준다.

 

그때 그때 최적해를 찾아가므로 그리디 알고리즘이라고 할 수 있다.

 

코드는 아래와 같다.

// source code github

https://url.kr/n1yhtf

hyun06000/coding_test_study_with_python

 

def solution(triangle):
    fore = triangle[0]
    for i in range(1, len(triangle)):
        curr = triangle[i]

        max_sum = []
        for j in range(len(curr)):
            if not j:
                sum = fore[j] + curr[j]
                max_sum.append(sum)
            elif j == len(curr) - 1:
                sum = fore[j - 1] + curr[j]
                max_sum.append(sum)
            else:
                sum = max(
                    fore[j - 1] + curr[j],
                    fore[j] + curr[j]
                )
                max_sum.append(sum)
        fore = max_sum

    return max(fore)

 

이런건 생각을 단순하게 하는 편이 더 좋은 것 같다.