programmers- lv.3 (정수 삼각형)

문제링크: 정수 삼각형

✍🏻 Information

	content
언어	python
난이도	⭐️⭐️⭐️
풀이시간	70분
제출횟수	∞
인터넷검색유무	yes

🍒 My Code

SUM = {}
def findsum(x,y,triangle):
    if x==0:
        return triangle[0][0]
    if (x,y) not in SUM:
        tmp = 0
        if y-1>=0:
            tmp = max(tmp,findsum(x-1,y-1,triangle)+triangle[x][y])
        if y<len(triangle[x-1]):
            tmp = max(tmp,findsum(x-1,y,triangle)+triangle[x][y])
        SUM[(x,y)] = tmp
    return SUM[(x,y)]

def solution(triangle): 
    answer=[]
    for i in range(len(triangle[-1])):
        answer.append(findsum(len(triangle[-1])-1,i,triangle))
    return(max(answer))

💡 What I learned

• 처음에는 아래와 같이 나올 수 있는 합을 다 구하고 그 중에서 제일 큰 수를 고르도록 했는데 시간초과가 났다. 은정이와 말하다가 깨닳았는데 예시에서 triangle[2][1]에 있는 1까지 도달하는 방법은 총 2가지가 있고 triangle[4][2]에 도달하는 방법은 6가지가 있는데 제일 큰 합을 구하는 것이기 때문에 이 모든걸 저장할 필요가 없었다. 나올 수 있는 합들 중 가장 큰 수만 저장하면 됐다. 그래서 MyCode에 있는 코드처럼 수정했더니 통과했다!
  결론은 더 가지를 쳐낼 필요가 있었다!!!

SUM = {}
def findsum(x,y,triangle):
    if x==0:
        return [triangle[0][0]]
    if (x,y) not in SUM:
        tmp = []
        if y-1>=0:
            tmp.extend([i+triangle[x][y] for i in findsum(x-1,y-1,triangle)])
        if y<len(triangle[x-1]):
            tmp.extend([i+triangle[x][y] for i in findsum(x-1,y,triangle)])
        SUM[(x,y)] = tmp
    return SUM[(x,y)]

• 다른 사람 풀이

def solution(triangle):
    for t in range(1, len(triangle)):
        for i in range(t+1):
            if i == 0:
                triangle[t][0] += triangle[t-1][0]
            elif i == t:
                triangle[t][-1] += triangle[t-1][-1]
            else:
                triangle[t][i] += max(triangle[t-1][i-1], triangle[t-1][i])
    return max(triangle[-1])

• DP 더 학습필요...