15650. N과 M (2)

문제링크: https://www.acmicpc.net/problem/15650

15649. N과 M (1)

15649번에 이은 n과 m 시리즈중 두번재 문제입니다. 여담으로 다른 블로그들을 찾아봤는데, 주로 삼성 코테에서 permuations와 combinations를 사용하지 못하게 하여서 이를 직접 구현할때 쓰는 알고리즘이라고 합니다. 조금 더 범용적으로 생각해보면 좋겠습니다.

Problem

전 문제와 동일하나, 조건이 하나 더 붙습니다. 수열이 감소하지 않는 수열이어야 한다는 점입니다.

Approach & Solution

1. Backtracking
   접근 방법은 전 문제와 동일하고 알맞은 조건을 붙혀서 문제를 바꾸어 주면 되겠습니다. 따라서 전 코드를 동일하게 사용하고, 이에 대한 설명은 전 문제 포스팅을 참고해주세요.

n, m = map(int,input().split())

result = []
mapping = [False] * (n+1)

def dfs(num):
  if num == m:
    print(' '.join(map(str,result)))
    return
    
  for i in range(1,n+1):
    if mapping[i] != True and (len(result) == 0 or i > result[-1]):
      mapping[i] = True
      result.append(i)
      dfs(num+1)
      result.pop()
      mapping[i] = False

dfs(0)

중간에 노드를 방문했는지 체크하는 조건문에, result의 마지막값보다 크거나 result가 비어있는지를 확인해서 result가 오름차순이 되게 조건을 겁니다.

if mapping[i] != True and (len(result) == 0 or i > result[-1]):

이 외의 풀이는 동일합니다.

2. Permutation

import itertools

n, m = map(int,input().split())
target = []
for i in range(1,n+1):
  target.append(i)
data = list(itertools.permutations(target,m))
answer = []
for i in data:
  temp = []
  for j in i:
    temp.append(j)
  temp.sort()
  if temp not in answer:
    answer.append(temp)

for i in range(len(answer)):
  print(' '.join(map(str,answer[i])))

처음엔 permutation으로 풀었습니다. sort()를 한번 거치고 answer안에 있는 값이면 예외처리를 하는방식으로 중복을 제거해 줬습니다.

Conclusion

기본의 변형은 생각보다 어렵지 않았습니다. 로직에 중요한 변화를 보지 못했거든요. 그저 조건문에 몇줄 추가하는 정도였습니다. 앞으로 있을 문제에서는 로직의 방향성을 바꾸는 문제가 있기를 바랍니다.