코딩테스트--정수 삼각형(프로그래머스 / 파이썬)

코딩테스트 연습 - 정수 삼각형

---

문제 설명

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

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

제한사항

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

입출력 예triangleresult

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

30

---

 

 

문제는 되게 간단하네요...?

3단계 첫 문젠데 좋습니다!

 

 

처음엔 무조건 큰 쪽으로 골라서 갈려했는데 30초 생각해보고 바로 철회 ㅋㅋㅋ

(이건 그냥 안될거 같네요..)

 

그래서 하나씩 하나씩 다 탐색해보려고 했습니다!

생각나는 건 재귀! 하면 거의... 시간 초과 나던데..

 

그래도 한번해보죠!

 

 

 

 

재귀

def solution(triangle):
    answer = 0
    save=0
    checklist=[]
    
    def find(index,count,save,checklist):
        
        if count==len(triangle):
            checklist.append(save)
            
        else:
            find(index,count+1,save+triangle[count][index],checklist)
            find(index+1,count+1,save+triangle[count][index],checklist)
                     
    find(0,0,0,checklist)
    return max(checklist)

1. 한 칸씩 내려가면서 선택해주고

2. 모든 값을 리스트에 저장 후 

3. 마지막엔 MAX함수로 가장 큰 값 출력!

 

...... 역시.. 시간 초과 ㅋㅋ

 

초과 나고 한번 찾아봤는데 와...  다들 신기하게 푸시더라고요

 

 

 

answer!

def solution(triangle):
    result = []

    for i in range(len(triangle)):
        for j in range(len(triangle[i])):
            if i==0:
                continue
            if j==0:
                triangle[i][j] += triangle[i-1][0]
            elif j==i:
                triangle[i][j] += triangle[i-1][-1]
            else:
                if triangle[i-1][j] >triangle[i-1][j-1]:
                    triangle[i][j] += triangle[i-1][j]
                else:
                    triangle[i][j] += triangle[i-1][j-1]
    return max(triangle[-1])

 

이게 모든 숫자들을 위의 숫자들 중 가장 큰 값을 찾아서 계속 더해주는 방법을 쓰더라고요

 

그니까 

여기 보시면 끝 숫자들은 하나의 값밖에 선택하지 못하기에 

왼쪽 끝은 7+3+8+2+4 해서 마지막에는 24가 남겠죠!

오른쪽 끝은 7+8+0+4+5 해서 숫자가 나오게 될 거예요

 

 

하지만 중간값들은 2개의 숫자 중 큰 수를 고르게끔 해야 되기에

값을 정해주어야 해요

여기서! 위에서 아래의 두 수를 고르는 게 아닌 아래 숫자에서 위의 숫자 중 큰 걸 고르기!

ex) 1을 기준으로 보면 3과 8중 8을 고르는 것! 그리고 더해주면 1의 자리에는 7+8+1이 오겠죠!

 

숫자를 적어볼게요 차례대로

		7
		(7+3),(7+8)
	7+3+8(18)	7+8+1(16)	7+8+0(15)
	(2+7+3+8)=20	(18+7),(16+4)	7+8+0+4
2+7+3+8+4=24	18+7+5=30	18+7+2=27	16+4+6=26	7+8+0+4+5=24

 

이렇게 되네요... (이해되시죠..?)

 

여하튼 숫자를 하나 잡고 위의 두 수중 큰 걸 더해주면서 계속 내려온다!

 

그리고 마지막 줄에서 가장 큰 값을 출력!

 

 

 

 

끝!

 

 

 

틀린 점이 있다면 댓 달아주세요!