[프로그래머스] 정수삼각형

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

삼각형의 각 층별로 나올 수 있는 최댓값들을 기록하였습니다.

다음 층을 계산할때 이전층의 최댓값에서 현재 더할 수 있는 값들을 더하고 더 큰 값들을 저장하였습니다.

2) 알고리즘

• DP

3) 풀이 코드

사용 언어 - Python

def solution(triangle):
    N = len(triangle)                                   # 삼각형의 높이
    dp = []                                             # 삼각형의 높이별 나올 수 있는 값

    dp.append(triangle[0])                              # 가장 위에층 설정
    n = 1                                               # 현재 높이
    while n < N:                                        # 현재 높이가 삼각형의 높이 보다 작으면 반복
        tmp = []                                        # 현재 층의 정답 경우의 수

        tmp.append(dp[-1][0] + triangle[n][0])          # 현재 층 가장 왼쪽의 값

        for i in range(n-1):                                            # 현재 층의 양 옆을 제외하고 나올 수 있는 경우의 수
            left = dp[-1][i]                                            # 이전 층의 왼쪽 값
            right = dp[-1][i+1]                                         # 이전 층의 오른쪽 값
            plus_value = triangle[n][i+1]                               # 현재 층의 값
            tmp.append(max(left + plus_value, right + plus_value))      # 현재 층의 값에서 이전 층의 값들을 각각 더했을때 최댓값

        tmp.append(dp[-1][-1] + triangle[n][-1])        # 현재 층 가장 오른쪽 값
        dp.append(tmp)                                  # 현재 층의 경우의 수 추가
        n += 1                                          # 층 증가
            
    return max(dp[-1])

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

삼각형의 높이별로 나올 수 있는 경우의 수가 2의 k제곱이였는데, 이 경우의 수만큼 2차원 배열을 만들려고 하였을때 메모리 초과 문제가 발생하였습니다.

(제한 사항에 삼각형의 높이가 500이 최댓값으로 2의 500제곱의 배열을 만들 경우 문제가 발생하였습니다.)

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

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

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다