개발자취

필자는 dp 방식으로 풀기 위해 메모이제이션에 사용할 배열을 잘못 생성하여 본 문제에 대해 12시간 이상을 고민했다. 독자는 그러지 마시길 바라며 글을 시작한다. 1. 문제 이해 _ 댐은 n개의 수문을 가지고 있다. 각각의 수문은 자체 용량과 물길을 가지고 있고, 하류에 영향을 줄 수 있다. 수문이 열렸을 때, 영향을 받는 지역은 홍수의 위험이 있다. 수문에 의한 예상 피해액은 지역의 인구의 수와 면적으로 계산할 수 있다. 수문 Gi의 유량이 Fi m3/hour 이고, 피해 비용이 Ci라고 하자. 댐에는 물이 Vm3 만큼 저장되어 있고, 이 물을 T시간 이내에 모두 비워내야 하는 상황이다. 이때, 수문을 어떻게 열어야 피해 비용이 최소가 되는지를 구하는 프로그램을 작성하시오. 예를 들어, 댐에 수문이 4..

독자님은 코딩테스트 문제를 풀면서 밤을 새본 적이 있나요? 저는 있습니다. :)... 독자님은 밤을 새시지 마시라는 의도로 본 글을 쓰게 되었습니다. 사실 구글링만 해보면 되는 결과를 안보고 풀겠다고 고집을 부리다가 또 밤을 새버렸네요. 지난 6월에 주에 한번 꼴로는 밤을 새본 것 같습니다. 이 문제도 그러한 문제 중 한 문제라고 보시면 되겠습니다. 정말 간단하게 풀어지는 풀이법은 dp로 이차원 배열로 정의해서 메모이제이션 방식으로 푸는겁니다. 그런데 저는 1차원 배열인 dp로 풀기 위해서 많은 시간을 사용했습니다. 고집을 포기하는 순간 행복해지는 거더라구요!_! 어쨌든. https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ ..