[백준][백트래킹] N과 M 2~12 번 모음

N과 M 2

15651번: N과 M (3)

 

- 순열 조합 라이브러리 이용할 수 있지만, 직접 구현하는 방법 공부

• 조합
  • start를 만들어두고 뽑은 수는 뽑지 못하게함

def comb(cnt,start):
  global n
  global m
  if cnt==m:
    print(*lst)
    return

  for i in range(start,n+1):
    lst.append(i)
    comb(cnt+1, i+1)
    lst.pop()


n,m=map(int,input().split())
lst=[]
comb(0,1) #골라서 나열 아니고 고르기만 하므로 조합

 

N과 M 3

15651번: N과 M (3)

 

• 중복 조합
  • start가 필요없음

def comb(cnt):
  global n
  global m
  if cnt==m:
    print(*lst)
    return

  for i in range(1,n+1):
    lst.append(i)
    comb(cnt+1)
    lst.pop()


n,m=map(int,input().split())
lst=[]
comb(0)

 

N과 M 4

채점 현황

 

• 고른 수열은 비내림차순이어야함 
  • -> 앞에 고른 수보다 작은 값일땐 continue

def comb(cnt):
  global n
  global m
  if cnt==m:
    print(*lst)
    return

  for i in range(1,n+1):
    if lst and lst[-1]>i:continue
    lst.append(i)
    comb(cnt+1)
    lst.pop()

n,m=map(int,input().split())
lst=[]
comb(0)

 

N과 M 5

15654번: N과 M (5)

 

• 순열
  • 뽑을 리스트 정해진 순열
  • 오름차순

def perm(cnt):
  if cnt==m:
    print(*result)
    return

  for i in range(len(lst)):    
    if not isSelected[i]:
      isSelected[i]=True
      result.append(lst[i])
      perm(cnt+1)
      isSelected[i]=False
      result.pop()
  

n,m=map(int,input().split())
lst=sorted(list(map(int,input().split())))
result=[]
isSelected=[False]*n
perm(0)

 

N과 M 6

15655번: N과 M (6)

 

• 조합
  • 뽑을 리스트 정해진 조합
  • 오름차순

def comb(cnt, start):
  if cnt==m:
    print(*result)
    return

  for i in range(start, len(lst)):
    result.append(lst[i])
    comb(cnt+1, i+1)
    result.pop()
  

n,m=map(int,input().split())
lst=sorted(list(map(int,input().split())))
result=[]

comb(0,0)

 

 

N과 M 7

15656번: N과 M (7)

 

• 중복순열
  • 리스트받은 중복순열

def perm(cnt):
  if cnt==m:
    print(*result)
    return

  for i in range(0, len(lst)):
    result.append(lst[i])
    perm(cnt+1)
    result.pop()
  

n,m=map(int,input().split())
lst=sorted(list(map(int,input().split())))
result=[]

perm(0)

 

N과 M 8

15657번: N과 M (8)

 

• 중복 조합
  • 비내림차순 중복 조합

def comb(cnt):
  if cnt==m:
    print(*result)
    return

  for i in range(0, len(lst)):
    if result and result[-1]>lst[i]: continue
    result.append(lst[i])
    comb(cnt+1)
    result.pop()
      

n,m=map(int,input().split())
lst=sorted(list(map(int,input().split())))
result=[]
comb(0)

 

📍N과 M 9

15663번: N과 M (9)

📍어려움

• 중복 불가
• 순열
• 정렬해놨기 때문에 이번에 뽑은 두번째 값이랑 for문을 돌아서 다음에 뽑을 두번째 값이 똑같으면 같은 배열이 만들어지는 것
  • for문 도는 것: 다른 경우의 두번째값을 뽑는 것
  • 그렇기 때문에 for문의 값이 동일한 경우 = 두번째값으로 같은 값을 뽑는 것
• idx==i 인경우만 continue 하면 이전의 idx 값만 고려하기 때문에 중복 발생
  • 세번째 수에서 첫번째에 뽑은 값이랑 같은 인덱스 값 고를 수 있음
  • -> 뽑은 인덱스를 리스트에 저장해놔야함

def perm(cnt,selectedIdx):
    global m
    if cnt==m:
        print(*result)
        return
  
    last=-1
    for i in range(len(lst)):
        if i in selectedIdx or last==lst[i]: continue
        result.append(lst[i])
        selectedIdx.append(i)
        last=lst[i]
        perm(cnt+1,selectedIdx) #다음번째 값을 찾으러 가는 것
        selectedIdx.pop()
        result.pop()


n,m=map(int,input().split())
lst=sorted(list(map(int,input().split())))
selectedIdx=[]
result=[]
answer=[]

perm(0,selectedIdx)

#사용한 반례

#입력
4 3
9 9 9 1

#출력
1 9 9
9 1 9
9 9 1
9 9 9

#처음에 idx==i했을때 출력값은
1 9 1 #중복된값까지 나옴
1 9 9
9 1 9
9 9 1
9 9 9

 

 

N과 M (10) 

15664번: N과 M (10)

• 9번상황에 비내림차순 -> 조합
• 중복불가

def comb(cnt, start):
  global m
  if cnt==m:
    print(*result)
    return

  last=0
  for i in range(start, len(lst)):
    if i in selectedIdx or last==lst[i]: continue
    result.append(lst[i])
    selectedIdx.append(i)
    last=lst[i]
    comb(cnt+1, i+1)
    selectedIdx.pop()
    result.pop()


n,m=map(int,input().split())
lst=sorted(list(map(int,input().split())))
selectedIdx=[]
result=[]

comb(0,0)

 

N과 M (11)

15665번: N과 M (11)

 

• 9번에서 중복 가능한 상황
  • 처음부터 다 탐색 -> start 필요없음

def comb(cnt):
  global m
  if cnt==m:
    print(*result)
    return

  last=0
  for i in range(len(lst)):
    if last==lst[i]: continue
    result.append(lst[i])
    last=lst[i]
    comb(cnt+1)
    result.pop()


n,m=map(int,input().split())
lst=sorted(list(map(int,input().split())))
result=[]

comb(0)

 

N과 M (12)

15666번: N과 M (12)

 

• 중복가능
  • 중복이 가능하려면 start가 없어야함
• 배열 비내림차순
  • 맨마지막 값보다 작은값이면 넘기는 것 
  • result and result[-1] > lst[i] 고려해줘야함
  • 11번이 2112 같은 경우도 가능했다면 12번은 안됨

def comb(cnt):
  if cnt == m:
    print(*result)
    return

  last = 0
  for i in range(0, len(lst)):
    if last == lst[i] or (result and result[-1] > lst[i]): continue
    result.append(lst[i])
    last=lst[i]
    comb(cnt+1)
    result.pop()

n, m = map(int, input().split())
lst = sorted(list(map(int, input().split())))
result = []

comb(0)