포도주 시식 - (Dynamic programming - 동적계획법) ★★★

 

30분 정도를 점화식을 구하는데 낑낑거리며 고민했지만,

결국 생각했던 식이 맞지 않아서 결국 다른 사람의 해설을 참조하였다.

 

i번째 와인에 대해서 나올 수 있는 경우는 세가지 인데,

a. i-1번째 경우에서 i번째에 술을 마시지 않는 경우

b. i-2번째 경우에서 i-1번째에 술을 마시지 않고 i번째에 술을 마시는 경우

c. i-3번째 경우에서 i-2번째에 술을 마시지 않고 i-1과 i번째에 술을 마시는 경우

 

 

여기서 x번째 경우는 저장되어 있는 경우의 수이니 dp배열의 값을 의미하고

술을 마시는 경우와 안 마시는 경우는 와인 양의 값이므로 위 코드에는 w배열의 값을 의미한다.

 

 

 

다이나믹 프로그래밍은

1. 점화식 구하기 (80%)

2. n=1이나 n=2 같은 for문에 걸리지 않는 초기값 설정해주기(20%)  가 전부인 것 같다.

 

빠르게 끝내고 크루스칼 알고리즘 코딩해보고 싶다.