[프로그래머스] 정수 삼각형(43105)
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/43105
문제
분류
-
알고리즘 분류
동적계획법, Dynamic Programming -
난이도
프로그래머스 Level 3 -
사용 언어
python 3
코드
try 1
전체 탐색, 재귀 호출
모든 경우의 수를 조사하는 전체 탐색을
트리 구조를 모방한 재귀 호출로 시도
def solution(triangle):
answer = returnMax(triangle, 0, 0, 0)
return answer
def returnMax(arr, indexY, indexX, sum):
sum += arr[indexY][indexX]
if(indexY == len(arr)-1): # 삼각형의 밑변인 경우 종료
return sum
# 삼각형의 그림 중 왼쪽 아래, 오른쪽 아래의 경로를 통했을 경우
# 각각의 값들을 재귀호출로 탐색
return max(returnMax(arr, indexY+1, indexX, sum),
returnMax(arr, indexY+1, indexX+1, sum))
결과
문제의 의도는 맞으나 효율이 너무 낮음
패인
전체 탐색으로 모든 경우의 수를 포함하니 중복 계산이 많이 들어감
또한 분류가 DP인데 메모이제이션은 하나도 하지 않았음을 깨닫고 처음부터 다시 시도함
try 2
동적 계획법
삼각형의 한 층씩 내려가면서
각 노드가 받을 수 있는 최댓값을 저장해 놓으면서 내려감
triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
부분과 같이 해당 노드는 바로 위 두 개의 노드 중 큰 값을 더해서 저장
def solution(triangle):
answer = 0
for i in range(1, len(triangle)): # 루트 제외
for j in range(len(triangle[i])):
if(j == 0): # 왼쪽 끝
triangle[i][j] += triangle[i-1][j]
elif(j == len(triangle[i]) -1): # 오른쪽 끝
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
answer = max(triangle[-1])
return answer
결과
백점이다 :)
마치며
코테 연습을 거의 안해봤어서 많이 헤맸다.(사실 엉뚱한 3번 정도의 시도가 더 있었다)
또한 코드 구성이 눈에 잘 들어오질 않는다. 이것은 추후에 보완 하도록 해야겠다.
Author And Source
이 문제에 관하여([프로그래머스] 정수 삼각형(43105)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dlwpdlf147/프로그래머스-정수-삼각형43105저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)