수다닷컴

질문 제목 : 질문 내용 :

통나무가 잘리는 길이에 비례해서 그 값이 결정되는 문제입니다.

----------------- 길이가 10인 통나무에 2,5,8 지점에 자르는 지점이 있다고 가정합니다
| | | (이때, 자르는 지점과 자르는 포인트 갯수는 프로그래머가 설정할 수 있습니다)
-----------------
258

총 길이가 10이므로 순차적으로 통나무를 자른다면 일단 길이가 10의 2지점에서 잘랐으므로 처음 비용은 10
그리고 2지점에서 통나무가 잘렸으므로 총길이가 8로 변합니다. 이때, 5지점에서 한번 더 잘렸으므로 비용은 8
마지막으로 통나무 길이는 총길이가 5로 변하고 8지점에서 한번 더 잘리면 비용은 5가 됩니다.

그리고 문제는 최소비용 이므로, 자르는 순서를 바꿔서,
길이가 10인 통나무의 5지점을 먼저 자른다면, 통나무는 각각 길이가 5인 통나무로 변하먼서 비용은 10,
그리고 두개로 나뉜 통나무중 2지점에 자르는 지점이 있는 통나무를 자르면 비용은 5
마찬가지로 전체 길이가 5인 통나무의 8지점의 통나무를 자른다면 비용은 5

자르는 방법에 따라서 비용이 달라집니다.

제가 구현한 코드는요,

#define max 100

//전역변수
int cut_point[max];int calculate_cost(int arr[], int numofcut, int start, int finish){
int target,len=finish-start;
if ( (target=find_middle(arr,start,finish) ) ==false ) //만약 중간값이 없다면,
return 0;

return len+calculate_cost(arr,numofcut,start,target)+calculate_cost(arr,numofcut,target,finish);
}

저기 위에 있는 int find_middle(int arr[], int start, int finish) 이건 어디다가 구현은 해놨는데,
노트라 잃어버린거 같습니다..;;

그러니까 위의 인자를 받아서, 위에있는 전역변수에 들어있는 지점들 중에 가장 중간값을 반환하는 함수입니다.

설명을 더 보태자면,처음 길이가 10인 통나무에서 잘리는 지점이 가장 중간값을 찾아서 리턴합니다.

위의 경우는 5이죠,

그리고 길이가 5인(0~5) 통나무를 함수의 인자로 건네 받았다면, 가장 중간값인 2를 리턴,

다른 길이가 5인(5~10)인 통나무를 함수의 인자로 건네 받았다면, 그 중간값인 8을 리턴합니다.

컴파일 할 수 있는 상황이 아니라 염치불구하고 올립니다 ㅡㅜ

궁금한 점은, 저기에 논리적이나 문법적 오류가 있는지 그리고 더 효율적으로 코딩할 수 있는지 그런게 궁금합니다.

틀렸다면 뭐가 틀렸는지도 알려주시면 감사하겠습니다

신청하기