https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3
전 이렇게 풀었습니다. (Python)
def solution(triangle):
if len(triangle) == 1 :
answer = triangle[0][0]
else :
low_tri_0 = [[0]]*(len(triangle)-1)
low_tri_1 = [[0]]*(len(triangle)-1)
for i in range(0, len(low_tri_0)):
low_tri_0[i] = triangle[i+1][0:len(triangle[i+1])-1]
low_tri_1[i] = triangle[i+1][1:len(triangle[i+1])]
a = solution(low_tri_0)
b = solution(low_tri_1)
if a>=b :
max_ab = a
else :
max_ab = b
answer = triangle[0][0] + max_ab
return answer
a = [[7], [3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]]
하고
solution(a) 하면 30 뜹니다.
님들도 30 뜨나요??
low_tri_a 와 low_tri_b 에는 처음에 입력된 triangle의 맨 위 꼭짓점을 뺀 뒤 밑에 생기는 두 개의 '한 계단 낮은' 삼각형이 입력됩니다. 그 두 개의 '한 계단 낮은 삼각형'들을 함수에 넣어서 나올 답들을 비교한 뒤 맨 위 꼭짓점을 더한 값이 최종 답이 될 것이며, 입력된 삼각형이 1층짜리 [[2]]라면 답은 2가 됨. 그래서 입력되는 삼각형이 1층인 경우와 아닌 경우를 나눈 뒤, 아닌 경우는 재귀함수를 통해 답이 나오도록 짰슴
이제 DP를 적용해보세요
그게머임
동적기획법 검색해 보세요
님이 올려놓은 소스 복사해서 넣어보려고 하는데 복사가 안됨.. 테스트 통과되나요?
복잡한걸 여러개로 나누어 푸는 방법이라고 되어 있는데 저 코드도 그런 아이디어에여 결국 층짜리 [[1], [2,3]]이 있으면 얘의 답은 1+ max(2,3) = 4 이므로, 1층짜리 [[3]]이 입력되면 3이 리턴되도록 짜고, 2층 이상이 입력되면 위에 말한 두 답안을 비교하는 과정이 계속 반복되는거져
저도 '결과보기'가 안되네여... 일단 화면에 나온삼각형은 결과값 30이 답이라는데 전 30 나왔어여
복잡한걸 여러개로 나누어 푸는건 분할정복 개념이고
동적 기획법의 경우 특정 지점까지의 계산 결과를 재활용 하는 경우가 많을 경우 재활용 하는 알고리즘 입니다
아하.. 그냥 재귀함수 때려넣으면 같은 계산을 반복하게 되는데 그걸 줄여야 되는구나;
218.233// 로그인해야 채점 되네요.. 전 맞았다고 뜸
어 근데 "시간초과"가 뜨네요?? ㄷㄷ 시간도 고려해야되는 줄 몰랐음 ㅠㅠㅠ
그럴거임 DP로 풀어야 되는 문제라서 ㅋ 구글 검색 ㄱㄱ
이거 높이가 500일때 해보셨나요
계속 시간초과 뜨네요.. ㅠㅠ