[ BOJ / 파이썬 ] 15657 N과M(8)

 

|  제출 1  |

# 중복조합 메서드 사용

import sys
input = sys.stdin.readline

from itertools import combinations_with_replacement


N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

for item in combinations_with_replacement(nums, M):
  print(*item)

: 중복을 허용해서 ( 본인 포함 ) 순서를 고려해서 뽑는 경우의 수 : 중복조합 메서드 사용한 풀이

 

 

 

|  제출 2  |

 

: 백트래킹 구현 실패 .. 🤕

 

# 백트래킹
import sys
input = sys.stdin.readline

from itertools import combinations_with_replacement


N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

keep = []
def recur(x):

  if x == M:
    print(*keep)
    return

  for i in range(N):
    if len(keep) == 0:
      keep.append(nums[i])
      recur(x+1)
      keep.pop()
      
recur(0)

 

이거 같은데 답이 안 나오는 것... 왜냐하면, 초기에 keep이 0일 때 한 번 들어간 이후로는 작동을 못 하니까.

 

스타트 이후의 다른 옵션을 같이 줘야하는것이었다. 생각해봐도 뭘로 기준 잡을 지 모르겠어서 결국 서치해서 찾아봤는데, 

 

import sys
input = sys.stdin.readline

from itertools import combinations_with_replacement


N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

keep = []
def recur(x):

  if x == M:
    print(*keep)
    return

  for i in range(N):
    if len(keep) == 0 or keep[-1] <= nums[i]:  # ✅ 여기에서 or로 추가옵션을 준다.
      keep.append(nums[i])
      recur(x+1)
      keep.pop()
      
recur(0)

 

: 항상 keep안에 들어갈 수 있는 수는 keep 내부 값 기준으로 찾으면 되는 것이었다!!

 

: 어차피 sorting해놓은 상태니까 작은 값 먼저 들어가서 마지막 keep값이랑 새로 들어갈 값을 비교해서 조건에 맞을 때 넣으면 된다. 

 

그리고 채점 결과

 

은근 머리 싸매고 고민해서 정답 처리 받아서 눈물 난다.. 흐.. 거의 비슷한 문제에서 약간씩만 틀어도 꽤 헷갈려진다 😓