코딩테스트> 동적 프로그래밍

백준 1904번

 

 

수열 문제를 풀듯이 점화식을 세워서 푸는 문제 유형이다. 

대부분의 문제가 그렇듯 나열을 하고 규칙을 찾아서 풀면 된다.

 

---

백준 12865번

 

처음에는 물건 가치의 최대값을 구하라고 해서 그리디 알고리즘을 이용하는 줄 알았다.

하지만 그리디 알고리즘을 사용하지 말아야 한다.

---

백준 11053번

 

---

백준 9251번

 

 

---

백준 1495번

 

---

백준 2655번

 

 

내가 쓴 답변

 

결과는 나오나 비효율의 극치인 것 같고 답이 틀리다고 나옴...

문제 푸는 원리는 같은데 말이지...

 

넓이 순서로 나열하고 순서를 깨지 않고 거기서 무게 순서대로 뽑는다는 원리는 맞게 접근했으나

최대값을 뽑는 동적프로그래밍을 어떻게 해야 할 지 아이디어가 떠오르지 않았음.

최대값을 가지고 역으로 뽑는 것도 떠오르지 않았음

 

원리를 이해하고 그걸 코드로 푸는 걸 했는데도 틀림... 

모범답안을 보고 곱씹어 보고 다시 생각해보니 이게 역시 맞는거 같다 굳