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

최근 코테를 보고 면접을 봤는데, 왜 자바로 풀지 않고 파이썬으로 풀었냐는 질문을 받았다.

 

한 번도 자바를 사용할 생각을 안해봤는데, 파이썬보다 자바를 사용하는 횟수를 늘려야겠다.

 

우선 오늘의 문제는 프로그래머스의 정수 삼각형 문제이다.

 

프로그래머스

728x90

문제

DP를 쉽게 접근해볼 수 있는 문제입니다.

 

접근 방법

일단 DP를 써야겠다라는 생각보단 전체적인 흐름을 이해했습니다. 각 경로의 합이 중첩되어 쌓이고 7 - 8 - 1 로 거치는 경우랑 7 - 3 - 1 로 거치는 경우처럼 목적지는 같지만 경로가 다를 수 있기 때문에 그 둘의 합을 비교하여 가장 큰 값을 저장해야겠다는 생각이 들었습니다.

 

그래서 먼저 각 경로에 따른 합을 저장하기 위해 입력되는 리스트와 똑같은 리스트를 생성해줬고 피라미드를 왼쪽에 붙은 계단식으로 생각을 해서 높이와 너비에 따라 계산을 했습니다.

발그림이라서 죄송합니다...

그렇게 생각해서 계산하고 각 경로에 따른 합이 저장된 리스트 중 가장 큰 값을 반환해줬습니다.

 

내가 푼 코드

def solution(triangle):
    intList = triangle
    SUM = [[0] * len(i) for i in intList] # 합계 적는 리스트
    width = height = 0
    for i in intList:
        for j in i:
            if height == 0 and width == 0: # 가장 처음 합
                SUM[height][width] = j # 윗줄이 없어서 더할 값이 없기 때문에 자기 자신 저장
            elif width == 0: # 만약 맨 왼쪽이라면
                SUM[height][width] = SUM[height-1][width] + j # 그 윗줄의 가장 왼쪽 값 가져와서 자기 자신과의 합 저장
            elif width == (len(i)-1): # 만약 맨 오른쪽이라면
                SUM[height][width] = SUM[height-1][width-1] + j # 그 윗줄의 가장 오른쪽 값 가져와서 자기 자신과의 합 저장
            else: # 그외 나머지
                SUM[height][width] = max(SUM[height-1][width] + j, SUM[height-1][width-1] + j) # 좌우 경로에 따른 값 중 큰 값 저장
            width +=1
        height   +=1
        width = 0 # 너비 초기화

    return max(map(max,SUM))