목록개미_나쁨 (1)

국문과 유목민

[DP] 개미전사

1. 문제 설명 - 개미가 배짱이네 집을 털러가는데 연속된 방을 털 수가 없다. 따라서 한 칸 을 넘어서 털어야 하는데 그럴 경우 가장 많이 털었을 때의 값을 묻는 문제 2. 코드 n = 4 array = list(map(int, "1 3 1 5".split())) df = [0]*(n) df[0] = array[0] df[1] = max(array[0], array[1]) for i in range(2, n): df[i] = max(df[i-1], df[i-2]+array[i]) df[n-1] # >> 8 3. 코멘트 - 항상 최선의 선택을 한다는 것을 알아둬야 한다. - 이전의 선택에 대한 계산 정보는 해당 위치에 저장이 된다. - 여기서 하나 신경써야할 점은 계산을 안하고 이전에 사용된 값을 그대로..
알고리즘_코딩테스트/이것이 코딩테스트다 2021. 12. 7. 23:23
이전 Prev 1 Next 다음