프로그래머스 정수 삼각형 (python, 파이썬)

• 문제

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

---

• 제한사항
  • 삼각형의 높이는 1 이상 500 이하입니다.
  • 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

---

• 입/출력

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

---

• 코드

def solution(triangle):
    answer = 0
    length = len(triangle)
    dp = [[]*length for _ in range(length)]
    
    for i, v in enumerate(triangle):
        for j in v:
            dp[i] = v
        
        for j in range(length-len(v)):
            dp[i].append(-1)
                
    for i in range(1, length):
        for j in range(length):
            if dp[i-1][j] == -1:
                dp[i][j] += dp[i-1][j-1]
            elif j-1 == -1:
                dp[i][j] += dp[i-1][j]
            else:
                dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])

    return max(dp[-1])

빈 곳을 -1로 채워넣는다.

 

7 -1 -1 -1 -1
3  8 -1 -1 -1
8  1  0 -1 -1
2  7  4  4 -1
4  5  2  6  5

 

아래로 내려오면서 값을 더할땐 바로위 또는 바로 왼쪽위의 값 둘중에 하나가 더해지게된다.

 

여기서 경우의수로 나누어주면된다.

 

1) 맨 왼쪽의 경우 왼쪽 위의 값이 없기 때문에, 바로위의 값과 더해준다.

 

2) 맨 오른쪽의 경우 바로 위의 값이 없기 때문에 왼쪽 위의 값과 더해준다.

 

3) 나머지 case의 경우는 바로 위의 값과 바로 왼쪽 위의 값 둘다 존재하기 때문에 둘중에 큰 값을 더해준다.

 

7 -1 -1 -1 -1
3  8 -1 -1 -1
8  1  0 -1 -1
2  7  4  4 -1
4  5  2  6  5

 

 7  -1 -1 -1 -1
10 15 -1 -1 -1
 8   1  0 -1 -1
 2   7  4  4 -1
 4   5  2  6  5

 

 7  -1  -1 -1  -1
10 15  -1 -1  -1
18 16 15 -1  -1
20 25 20 19  -1
24 30 27 26 24

 

마지막 줄에서 max를 통해서 값을 찾으면 된다.

 

 

p.s) 위의 코드로 실행할시 효율성에서 아래와 같은 시간이 걸릴 수 있습니다.

 

제가 단순히 이중 for문을 돌때 -1인 부분은 padding 처리를 진행했기 때문에 굳이 값을 탐색할 필요가 없다.

그 부분을 제외해주는 if dp[i][j] == 1: continue 하나만 적어줬을 뿐인데 아래와 같이 시간이 훨씬 단축됐다.

사소한 부분이지만 그리고 이 문제는 통과했지만 조금 더 세밀하게 신경쓰면 더 좋을 것 같다,

 

---

• 출처

programmers.co.kr/learn/courses/30/lessons/43105?language=python3