이것이 코딩테스트다 - 개미전사

1 3 1 5

 

1

1 1

1 5

3

3 5

1

5

 

 

이 문제를 보고 바로 점화식을 세워야겠다는 어떻게 하는 걸까?

점화식은 참 신기하다. 항들의 관계로 답을 풀어간다는 게 참 나에게는 아직 어렵다.

그럼에도 한번 더 풀어본다.

이 문제에서는 i번째를 골랐을 때 i-2번째의 값과 더한 값과 i-1번째 값 하나만 골랐을 때 이 둘중에 큰 것이 d[i]의 값이 되게 풀었다. 내가 생각한 점화식의 핵심은 이렇다. 가정을 최소한으로 만들어서 3가지 가정을 만든 후에 일일히 대입해보는 것이다. 그렇다면 4번쨰 가정을 공식에 대입했을 때 풀리면 점화식이다. 논리적으로 답이 도출안될 때 이렇게 풀이하면 될 것 같다. 하지만 우리는 논리적으로 구하는 연습을 해야한다. 

 

i번째까지의 최대값을 d[i]에 저장하는 것 제일 중요하다.

 

3번째까지의 최대값을 구한다고 생각해보자.

우선 1번째까지의 최대값은 1이 들어간다. 

2번째까지의 최대값은 1과 3 둘중 큰것이니 3이 들어간다.

3번째까지의 최대값은 1+1과 3 둘중 큰것이다.

그렇다면 4번째까지의 최대값은? 마찬가지이다 d[3]과 d[2]+array[4]의 값을 비교해보면 된다.

점점 최대값이 커지는 오름차순이기 때문에 i-1번쨰와 i-2번쨰 + i번째를 비교할 수 있는 것이다.

연습하자..

 

 

소스 코드는 이렇다.

 

n = int(input())
array= list(map(int,input().split()))

d = [0]*100

d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2,n):
  d[i] = max(d[i-1], d[i-2] + array[i])

print(d[n-1])