자르기
-
[문제해결을 위한 창의적 알고리즘] 두부 자르기 (고급, p207)알고리즘 2017. 2. 19. 19:14
이 문제는 한국정보올림피아드에 출제되었던 문제인데, 굉장히 어렵다고 알려져 있다. 실제로 어떻게 동적계획법을 세워야할지 감이 잘 오지 않는다. 따라서 먼저, 완전 탐색을 이용한 방법으로 푸는 방법을 알아보고자 한다. import java.util.Scanner; public class TofuCutSol209 { // 두부가 선택되었는지 확인하기 위한 배열public static int[][] chk = new int[20][20];// 가격 배열, 풀이에서는 26x26배열이지만 이미 F가 마지막 배열이므로 26까지 필요 없다. 아래에서 A~F까지 알파벳에서 A를 빼서 배열 위치를// 확인하고 있으므로 6x6을 지정해야 한다. 자바에서 배열 초기화 방법이 C와 다르므로 아래와 같이 초기화했다.public..