BOJ 5638번 수문

5638번: 수문

 

각 수문의 유랑과 비용을 이용해, 조합 가능한 유량의 최소비용을 테이블에 저장하여 풀 수 있는 문제였다. 다만 약간의 함정이 2곳에 있었다.

 

---

수문의 정보가 다음과 같이 주어진다면, 배출 가능한 유량과 비용의 테이블을 만들 수 있다.

 

---

여기서 요구되는 배출 가능 유량이 4000이라면? 첫 번째 함정이라고 느낀 부분이다. 

 

 

이 부분은 당연히 200 비용으로 처리되어야 하고, 실제 구현을 해보면 간단하게 처리할 수 있다. (cpp 141 line)

하지만 자칫 잘못하면 처음 아이디어를 낼 때 생각이 안드로메다로 떠날 수 있다... (내가 그랬다)

 

 

두 번째 함정이라고 느낀 부분은, 위와 동일한 예제에서 3000의 유량을 요구하는 경우이다.

3000 유량이면 1번 수문과 2번 수문을 열어 250 비용으로 처리할 수 도 있지만.

 

 

이 부분을 처리하기 위해 합병 정렬을 차용하여 구현하였다. (cpp 85 line)

---

 

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지

두 번째 부분을 깔끔하게 해결했다는 느낌이 아니라 조금 찝찝하다. 뭔가 더 좋은 아이디어가 있을까?

피보나치만큼 간단한 DP 문제는 아니지만 굳이 난이도를 나누자면 어렵지 않은 축에 속하는 문제라는 느낌을 받았다.

무엇보다 코딩 스타일이 너무 이상하다, 천천히 내 스타일을 정리해 나가야 한다.