[책-알고리즘퍼즐68]4.막대자르기

문제

길이 n cm의 한 막대를 1cm 단위로 자른다. 단, 하나의 막대는 한번에 한 사람만이 자를 수 있다. 잘린 막대가 3개면 동시에 3명이 자를 수 있다. 최다 m명이 있을 때 막대를 자르는 최소 횟수를 구하시오. 예를 들어 n=8, m=3일때 4번 자를 수 있다.

 

난이도

IQ 70

 

목표시간

10분

 

문제풀이(사용언어:C#, 작성도구:VisualStudio2019)

//20.01.09
//
//

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _4_CutStick
{
    class Program
    {
        static void Main(string[] args)
        {
            int STICK_LENGH = 100;
            int MEMBER_COUNT = 5;
            
            double depth = Math.Ceiling(Math.Log(STICK_LENGH, 2));
            Console.WriteLine("length :: " + STICK_LENGH);
            Console.WriteLine("members :: " + MEMBER_COUNT);
            Console.WriteLine("depth :: " + depth);

            double resultCnt = 0f; //최종 자르는 횟수
            int totalCutCnt = 0;   //좌우로 2의 제곱으로 증가하면서 자르는 횟수
            int remainCut=0;       //사람이 부족해서 다음 스텝에서 잘라야 하는 횟수

            for (int i=0; i<depth; i++)
            {
                totalCutCnt++;
                int cutCnt = (int)Math.Pow(2, i);

                if (MEMBER_COUNT < cutCnt)
                {
                    remainCut += cutCnt - MEMBER_COUNT;
                }

                //마지막 뎁스 일때
                if (i == (depth-1) )
                {
                    //2의 제곱수가 아니면 홀수 단위로 자르게 되어 추가적으로 잘라야한다.
                    if ( (Math.Log(STICK_LENGH,2) - (int)Math.Log(STICK_LENGH,2) ) != 0)
                    {
                        int addCutCnt = (int)Math.Pow(2, i - 1);

                        if(MEMBER_COUNT < addCutCnt)
                        {
                            totalCutCnt++;
                            remainCut += addCutCnt - MEMBER_COUNT;
                        }
                    }
                }
            }

            resultCnt = totalCutCnt + Math.Ceiling((double)remainCut/MEMBER_COUNT);
            Console.WriteLine("least cut count::" + resultCnt);

        }
    }
}

 

문제정답(사용언어:python)

1. solution_1은 문제 그대로를 재귀로 옮긴 방식

2. solution_2 발상의 전환. m명이 n막대를 자르는게 아닌 m명이 1cm 막대를 n cm 막대로 붙여 나간다고 생각.

 

##solution_1
def cutbar(m, n, current): # current는 현재 막대의 개수
    if current >= n:
        return 0 # 잘라내기 완료
    elif current < m:
        return 1 + cutbar(m, n, current*2) # 다음은 현재의 2배가 된다
    else :
        return 1 + cutbar(m, n, current+m) # 가위 수만큼 증가

print(cutbar(3, 20, 1))
print(cutbar(5, 100, 1))

##solution_2
def cutbar(m, n): 
    count = 0;
    current = 1 # current는 현재 막대의 길이
    while n > current:
        print(current)
        current += current if current <m else m
        count +=1
    print(count)

cutbar(3, 20)
cutbar(5, 100)

 

배운점

깊이 우선 방식을 이용한 재귀구현.

깊이 우선 방식의 경우 모든 탐색 경로를 찾을시에는 메모리 공간을 아낄수 있다.

너비 우선 탐색은 가장 빠른 탐색 경로 하나를 발견해야하는 경우에는 유리하다.