[알고리즘 수학] 막대자르기

길이가 100인 막대를 잘라 길이가 1인 조각 100개를 만들어야 한다. 여러 조각을 한꺼번에 자를 수 있다고 가정할 때 자르는 최소 횟수는 몇번인가?

막대의 길이가 n일때 최소 횟수만에 자르는 알고리즘을 설명하라.

문제출처) 길벗 - 알고리즘 퍼즐

 

문제풀이)

이 문제는 정보올림피아드 예선 문제에 자주 출제되는 유형으로 다음과 같이 절반씩 잘라 가는 유형으로 생각하면 됩니다.

100 = 50 * 2

50 = 25 * 2

25 = 13 + 12 (여기서 13 크기를 기준으로 생각함)

13 = 7 + 6 (여기서 7 크기를 기준으로 생각함)

7 = 4 + 3 (여기서 4 크기를 기준으로 생각함)

4 = 2*2

2 = 1*1

즉 7번이면 100인 막대를 1 크기로 모두 자를 수 있습니다.

여기서 아이디어는 절반씩 잘라 간다는 것입니다.

즉 2까지는 1회, 4까지는 2회,8까지는 3회,16까지는 4회, 32까지는 5회, 64까지는 6회,128까지는 7회로 가능합니다.

즉 2^k 이 n의 값 이상이라면 k 회수 안에서 자를 수 있습니다.

 

C++

int main(){
    int n,k;
    cin >> n;
    for(k=1; 1<<k < n; k++);
    cout << k;
}