동적계획법(DP) 대표문제2 - ROD CUTTING(막대기 자르기)
동적계획법(Dynamic Programming, DP)는 가장 많이 쓰이는 알고리즘 기법이자 기초이다. 하지만 그만큼 다양한 응용과 아이디어가 필요해서 완벽하게 익히기도 어렵다. 이론은 듣기에 간단하지만 문제에 따라 응용이 매우 어려운 것이다. 때문에 다양한 문제를 풀어보며 직접 익히는 방법밖에는 없다. 특히, 점화식을 세우고 점화식에 따라 DP 해법을 저장하는 배열을 선언하는 연습을 많이 해 봐야 할 것이다. 동적계획법을 사용해 풀 수 있는 대표 문제 중 두번째로 ROD CUTTING(막대기 자르기) 문제에 대해 소개하려고 한다. 문제를 푸는데 사용한 언어는 java 이다. 이 문제를 보기 전에, 동적계획법에 대한 아무런 사전 지식이 없다면 아래 포스팅을 먼저 참고 바란다.[동적계획법 풀이 대한 간략한..
