[BOJ 1932][백준 1932번] 정수 삼각형 (파이썬 풀이)

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

🤔 문제 설명 및 입출력

---

 

 

✍ 접근 방법

---

이동할 수 있는 경로가 천차만별이고, 그 과정을 다 일일이 추적하기에는 굉장히 복잡했기 때문에 메모이제이션으로 해결해야겠다는 생각이 들었다. 

 

메모이제이션의 기본 아이디어는 입력값을 받는 배열 이외에 새로운 배열을 만들어, 현재 필요한 값을 구할 때 새로운 배열의 이전 값을 참조하여 푸는 방식으로 접근하는 것이다.

 

문제 예시가 트리와 유사하게 생겼기에, 각 입력값을 노드라고 생각하고 각 노드까지 도달하는데의 최대값을 저장하면 된다고 생각했다.

 

memo라는 리스트를 하나 선언한 다음, 최대값들을 우겨넣기로 했다.

 

근데 여기서 최대값들을 어떻게 관리할까? 라는 의문이 들었다. memo의 인덱스가 삼각형의 레벨과 일치하기에, memo의 각 요소는 삼각형의 node를 관리해야한다. 그렇기 때문에 memo는 2차원 배열으로 선언 되어야할 필요가 있는데, 나는 단순 리스트보다 사전을 사용하는 것이 내가 사용하기도 편하고, 추적하기도 편할 것이라 생각해서 사전을 내포한 리스트. 즉 [{  }, {  }, {  },......] 꼴로 memo를 사용하기로 했다.  

 

 

👨‍💻 소스 코드

---

• 파이썬

 

N = int(input()) 


tree = [ [] for _ in range(N)]
memo = [ {} for _ in range(N)] # 삼각형의 경로값을 저장할 배열


for i in range(N):
    tem = list(map(int,(input().split())))
    tree[i] = tem

memo[0][0] = tree[0][0] # 초기값 설정 , memo의 0번 요소에 key == 0으로 tree[0][0]을 넣었다


# oidx : outer index / iidex: inner index
# oidx는 리스트의 각 요소에 접근할 때 사용
# iidx는 요소(dict)의 키 값으로 사용됨 

for oidx in range(1,len(tree)):
    for iidx in range(len(memo[oidx-1])):

        # 현재 경로의 최대값 memo[oidx][iidx] / memo[oidx][iidx+1] 은
        # 직전 까지의 경로 최대 합 memo[oidx-1][iidx] 에서 현재 순회중인 값 tree[oidx][iidx]와 tree[oidx][iidx+1]
        # 을 더한 값으로 결정된다.

        # num1과 num2이라는 변수를 선언하여  직전까지 경로 최대합 + 현재 순회중인 값 을 저장해놓는다
        num1 = memo[oidx-1][iidx]+ tree[oidx][iidx]
        num2 = memo[oidx-1][iidx]+ tree[oidx][iidx+1]

        # 근데 만약에 이미 memo[oidx][iidx] / memo[oidx][iidx+1]의 value가 존재한다면
        # max()를 이용해서 최대 값이 그 자리를 차지 할 수 있도록 한다.
        if memo[oidx].get(iidx):
            memo[oidx][iidx] = max(num1, memo[oidx][iidx])

        else:
            memo[oidx][iidx] = num1

        if memo[oidx].get(iidx+1):
            memo[oidx][iidx+1] = max(num2,memo[oidx][iidx+1])
        else:
            memo[oidx][iidx+1] = num2

 

🔥 강평

---

다른 사람의 풀이를 보니까, memo를 따로 선언하는 것이 아니라, tree 리스트 자체를 수정하면서 메모이제이션 기법을 활용하고 있었다. 이와 같은 풀이법은 별개의 리스트를 선언한 내 풀이보다 메모리 효율이 더 좋다. 내가 아직 DP에 익숙치 않은 것 같다는 생각이 들었다. 좀 더 화이팅 해보자.

 

# BOJ dbtjd1928 님 풀이

n = int(sys.stdin.readline())
tri = [[int(sys.stdin.readline())]]
for i in range(n-1):
    tri.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            tri[i][0] += tri[i-1][0]
        elif j == i:
            tri[i][j] += tri[i-1][j-1]
        else:
            tri[i][j] += max(tri[i-1][j-1], tri[i-1][j])

print(max(tri[n-1]))

이런 깔끔한 코드를 자연스럽게 만들 수 있는 사람이 되고 싶다