68 - (파이썬) 확인문제: 기본 형태

# 여러 개의 테이블에 나누어 앉을 때, 한 사람만 앉는 테이블이 없도록 그룹을 지어보자. (단, 인원 수를 나누는 패턴만 구한다.)

eg) 6명일 때, 다음 네 가지 경우를 갖는다.

2명+2명+2명

2명+4명

3명+3명

6명

 

#한 테이블에 앉을 수 있는 최대 인원은 10명일 때, 

 

- step 1) 화살표 만들기

전체사람수 = 6

#그래프를 나타내는 함수에 노드에 적힌 수를 매개변수로 지정한다
def graph(nod):
  #화살표를 2명부터 6명까지 뽑아주기 위해 for 반복문을 이용한다
  #한 테이블에 앉을 수 있는 최대 인원은 10명이므로 nod와 10명 중 작은 것을 골라서 돌리게 한다
  for i in range(2, min(nod, 10)+1):
    print(i)

graph(전체사람수)
>>>
2
3
4
5
6

 

- step 2) {nod}와 {i} 화살표를 만드는 것을 확인하는 단계를 추가

전체사람수 = 6

#그래프를 나타내는 함수에 노드에 적힌 수를 매개변수로 지정한다
def graph(nod):
  print(f"{nod}에 진입")
  #화살표를 2명부터 6명까지 뽑아주기 위해 for 반복문을 이용한다
  #한 테이블에 앉을 수 있는 최대 인원은 10명이므로 nod와 10명 중 작은 것을 골라서 돌리게 한다
  for i in range(2, min(nod, 10)+1):
    print(f"{i} 화살표를 만듦")
    #재귀함수로 호출하게되면
    graph(nod-i)
    print()

graph(전체사람수)
>>>
6에 진입
2 화살표를 만듦
4에 진입
2 화살표를 만듦
2에 진입
2 화살표를 만듦
0에 진입


3 화살표를 만듦
1에 진입

4 화살표를 만듦
0에 진입


3 화살표를 만듦
3에 진입
2 화살표를 만듦
1에 진입

3 화살표를 만듦
0에 진입


4 화살표를 만듦
2에 진입
2 화살표를 만듦
0에 진입


5 화살표를 만듦
1에 진입

6 화살표를 만듦
0에 진입

 

 

요고를 이해하기 위해 파이썬 튜터에 돌려보면

 

- step 3) counter로 모든 경우의 수 구하기

전체사람수 = 6
counter = 0

def graph(nod):
  #print(f"{nod}에 진입")
  #nod가 0명이 되는 경우만 세어준다
  if nod == 0:
    #외부에서 스택을 변경하가 때문에 global을 쓴다
    global counter
    counter += 1
  for i in range(2, min(nod, 10)+1):
    #print(f"{i} 화살표를 만듦")
    graph(nod-i)

graph(전체사람수)
print(counter)
>>>
5

 

⚠︎ 아 근디, 중복을 세어서 5개나 나왔네

 

- step 4) 중복을 삭제한다

전체사람수 = 6
counter = 0

#이전에 몇 명을 앉혔는지 이전 화살표에 적힌 숫자를 만들어주고
def graph(nod,preArrowNumber):
  if nod == 0:
    global counter
    counter += 1
  #2와 이전 화살표에 적힌 숫자 중 큰 것을 선택하는 조건을 만들어준다
  for i in range(max(2,preArrowNumber), min(nod, 10)+1):
    #매개변수는 i를 전달해서 말해준다
    graph(nod-i, i)

#이전 화살표의 항등원은 0
graph(전체사람수,0)
print(counter)
>>>
4

 

#따라서 100명의 사람이 하나 이상의 테이블에 나누어 앉는 패턴의 경우의 수를 구하면

전체사람수 = 100
counter = 0

#이전에 몇 명을 앉혔는지 이전 화살표에 적힌 숫자를 만들어주고
def graph(nod,preArrowNumber):
  if nod == 0:
    global counter
    counter += 1
  #2와 이전 화살표에 적힌 숫자 중 큰 것을 선택하는 조건을 만들어준다
  for i in range(max(2,preArrowNumber), min(nod, 10)+1):
    #매개변수는 i를 전달해서 말해준다
    graph(nod-i, i)

#이전 화살표의 항등원은 0
graph(전체사람수,0)
print(counter)
>>>
437420

 

---

https://replit.com/@wh3308/LongtermDramaticPress