[프로그래머스] 정수 삼각형 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 올 수 있는 이전의 길의 결과 중 가장 최댓값을 계속 적으로 선택하여 오면 된다.

하여 처음부터 다음 길을 갈 때 다음 길에 지금까지 온 길의 합을 계속 저장하고, 마지막에 도착했을 때 마지막 길들 중 최댓값을 구하면 해결되는 문제이다.

 

1. 이전의 길의 결과를 저장할 리스트를 생성한다. result = list()
2. 제일 처음 출발점의 값을 추가한다. result.append(triangle[0])
3. 이전 값은 처음부터 마지막 전까지 길의 값을 추출해야 한다. for i in range(len(triangle) - 1)
4. 각 가로열의 길의 결과를 한 번에 저장할 리스트를 생성한다. li = list()
5. 다음 값은 구하려는 각 가로열의 개수만큼 반복한다. for j in range(len(triangle[i + 1]))
6. 만약 구하는 위치가 제일 앞 길이라면 if (j == 0)
7. 해당 위치의 이전 길은 무조건 이전 가로열 길의 제일 앞 길이다. 하여 이전 길의 값과 구하려는 다음 길의 값을 더하여 추가한다. li.append(result[i][j] + triangle[i + 1][j])
8. 만약 구하는 위치가 제일 뒷 길이라면 elif (j == len(triangle[i + 1]) - 1)
9. 이전 길은 무조건 이전 가로열 길의 제일 뒷 길이다.  하여 이전 길의 값과 구하려는 다음 길의 값을 더하여 추가한다. li.append(result[i][j - 1] + triangle[i + 1][j])
10. 반면에 구하는 위치가 중간 길이라면 else
11. 이전 길은 2가지의 선택지가 생긴다. 하여 이전 길의 2가지 선택지 값 중 더 큰 값을 가져와 다음 길의 값을 더하여 추가한다. li.append(max(result[i][j - 1], result[i][j]) + triangle[i + 1][j])
12. 각 가로열의 모든 길을 구했으면 구한 결과를 추가한다. result.append(li)
13. 마지막 가로열까지 각 길별 올 수 있는 최댓값의 경우를 구했으면 마지막 가로열 길의 값 중 최댓값을 저장한다. answer = max(result[-1])

반응형

3. 소스코드

def solution(triangle):
    answer = 0
    
    result = list()
    result.append(triangle[0])

    for i in range(len(triangle) - 1):
        li = list()
        for j in range(len(triangle[i + 1])):
            if (j == 0):
                li.append(result[i][j] + triangle[i + 1][j])
            elif (j == len(triangle[i + 1]) - 1):
                li.append(result[i][j - 1] + triangle[i + 1][j])
            else:
                li.append(max(result[i][j - 1], result[i][j]) + triangle[i + 1][j])

        result.append(li)
    
    answer = max(result[-1])
    
    return answer