Python 23제] 깊이 우선 탐색을 활용한 막대자르기

출처 : 반크 독도 포스터

 

문제]

길이 8m의 막대를 3명이서 1m단위로 자를려고 할 때 몇 번이면 1m 막대가 될 수 있는지 프로그램을 작성하시오. (단, 하나의 막대는 한 사람만 자를 수 있다.)
8 -> 4, 4 로 자른다 1번
4, 4 -> 2, 2, 2, 2로 자른다 2번
2,2,2 -> 1,1,1,1,1,1로 자른다 3번
2 -> 1,1로 자른다 4번
그러므로 총 4번을 자르면 8m 막대가 1m막대로 만들수 있게 된다.

 

입력 예시1]
20, 3

출력 예시1]
8


입력 예시2]
100, 5

출력 예시2]
22

 

 

참고풀이]

#x: 막대기 총수
#y: 막대기 자를 인원수
#n: 현재 자를 막대기 개수
def cutDef(x,y,n):
    if n>=x: #자를 막대기가 1m가 되면 작업을 끝낸다.
        return 0
    elif n<y: #인원수로 잘라내 막대기 수
        return 1+cutDef(x,y,n*2) 
    else: #인원수가 적으면 현막대기수에 인원수를 더한다.
        return 1+cutDef(x,y,n+y) 
    
#main 부분
a,b=map(int,input().split(' '))
print(cutDef(a,b,1))

 

 

참고풀이 결과]

 

 

 

대한민국의 아름다운 영토, 독도