5-2 마무리 확인문제 1번

5-2 함수의 활용 마무리 확인문제 1번

Q. 문제

패밀리 레스토랑에서 여러 개의 테이블에 나누어 앉으려고 합니다.
이때 한 사람만 앉는 테이블이 없게 그룹을 지어야 합니다.
6명 같은 경우는 4가지의 경우를 생각할 수 있습니다.
2명 + 2명 + 2명 , 2명 + 4명, 3명 + 3명, 6명
한 개의 테이블에 앉을 수 있는 최대 사람의 수는 10명입니다.
100명의 사람이 하나 이상의 테이블에 나누어 앉은 패턴을 구하세요

A. 나의 풀이

#앉힐수있는최소사람수
min_people = 2
#앉힐수있는최대사람수
max_people = 10
#전체사람의 수
total_people = 100
#횟수저장 딕셔너리
memo = {}

def problem(extra, sit):
    #남은사람수, 앉힌 사람수를 묶어 딕셔너리의 키 변수에 문자열로 저장
    key = str([extra, sit])
    #종료 조건, 이미 계산했던 경우이면 종료
    if key in memo:
        return memo[key]
    if extra < 0:
        return 0 #무효이므로 0을 리턴
    if extra == 0:
        return 1 #유효하므로 수를 세기 위해 1을 리턴

여기까지 밖에 못 풀었다.. 물론 결과는 오류 덩어리

A. 답지 풀이

#앉힐수있는최소사람수
min_people = 2
#앉힐수있는최대사람수
max_people = 10
#전체사람의 수
total_people = 100
#횟수저장 딕셔너리
memo = {}

def problem(extra, sit):
    #남은사람수, 앉힌 사람수를 묶어 딕셔너리의 키 변수에 문자열로 저장
    key = str([extra, sit])
    #종료 조건, 이미 계산했던 경우이면 종료
    if key in memo:
        return memo[key]
    if extra < 0:
        return 0 #무효이므로 0을 리턴
    if extra == 0:
        return 1 #유효하므로 수를 세기 위해 1을 리턴
    #재귀 처리
    count = 0
    #한 테이블당 앉을 수 있는 사람 2-10명
    for i in range(sit, max_people + 1):
        count = count + problem(extra-i, i)
    #메모화 처리, 딕셔너리에 경우의 수 저장
    memo[key] = count
    #종료, 모든 경우의 수 리턴
    return count

print(problem(total_people,min_people))
print(memo['[100, 2]'])

답지 결과

코멘트

파이썬에서의 재귀함수, 메모리화에 대해서 처음 배웠는데
막상 코드를 짜려니 어떻게 해야할지 하나도 모르겠당...