[백준] 1094 - 막대기 (재귀 풀이) (python)

1094번: 막대기

포인트

문제 설명이 복잡하지만 그냥 64를 포함하여 그걸 절반으로 나눠서 나올 수 있는 수들 (64, 32, 16, 8, 4, 2, 1) 중 몇 개 수의 합으로 X를 만들 수 있는지를 묻는 문제입니다. 풀고 나서 보니 반복문을 많이 활용했던데 저같은 경우는 나누는 과정에서 재귀 함수를 활용했습니다. 

코드

	x = int(input())
	def make_stick_half(stick, target, count):
	# 막대의 길이가 만드려는 길이와 같은 경우
	if stick == target:
	# 누적된 갯수 리턴하며 재귀 탈출
	return count
	# 막대의 길이가 만드려는 길이보다 긴 경우
	elif stick > target:
	# 그 막대는 쓸 수 없으니 절반 길이의 막대로 재귀 호출
	return make_stick_half(stick // 2, target, count)
	# 막대의 길이가 만드려는 길이보다 짧아진 경우
	else:
	# 그 막대는 쓸 수 있으므로 target의 길이에서 막대 길이만큼 빼주고 카운트도 올린다. 이 후엔 그 절반 길이의 막대로 확인해야하므로 반으로 나눠 재귀 출발
	return make_stick_half(stick // 2, target-stick, count + 1)
	# 가장 긴 막대의 길이 64로 재귀 출발
	answer = make_stick_half(64, x, 1)
	print(answer)

view raw boj_1094.pyt hosted with ❤ by GitHub