15649 ~ 15666번을 풀어보았다.
재귀를 공부하고 다시 한 번 이해하는 데 많은 도움이 됐다.
솔직히 막힌적도 너무 많고 도저히 모르겠으면 다른 블로그를 참조한 적도 많다;;; 그저 반성..
일단 기본이 되는 코드들만 올려놓겠다. (다른 문제를 푸는게 근간이 되는 문제들?)
15649 / N과 M(1)
n, m = map(int, input().split())
numbers = []
def dfs():
if len(numbers) == m:
print(' '.join(map(str, numbers)))
return
for i in range(1, n+1):
if i not in numbers:
numbers.append(i)
dfs()
numbers.pop()
dfs()
15663 / N과 M(9)
from sys import stdin
n, m = map(int, input().split())
array = sorted(list(map(int, stdin.readline().split())))
numbers = []
visited = [False]*n
def dfs():
global visited
if len(numbers) == m:
print(' '.join(map(str, numbers)))
return
temp = 0 #같은지 확인?
for i in range(n):
if not visited[i] and temp != array[i]:
numbers.append(array[i])
visited[i] = True
temp = array[i]
dfs()
visited[i] = False
numbers.pop()
dfs()
재귀가 너무 복잡해서 파이썬튜터로 돌렸다.
다들 어려운 개념이 있어서 코드의 흐름파악이 어렵다면 파이썬 튜터를 사용해 보시길...매우 유용하다.
여기서 어려운 점은 중복되는 숫자가 있더라도 다른것으로 생각해야하고,
그렇다고 같은 배열을 출력하면 안된다는 점이었다.
중복되는 숫자를 다르게 생각하는 것은 인덱스기준으로 다르게 생각해서 처리하면 되니까 괜찮았는데
같은 배열을 출력하는 안된다는 점이 힘들었다.
예를 들어 중복되는 9가 2개가 있을 때 각자 9(1), 9(2)라고 한다면
1 9(1) 9(2) 를 출력했을 때 1 9(2) 91(1)은 출력을 같이 할 수 없다는 것이다. 둘 중에 하나만 출력해야 한다.
그래서 이를 해결하기 위해 temp라는 변수를 만들었다.
이 변수로 중복되는 숫자들이 다르더라도 반복될 수 없도록 한다.(아래 사진 참고)
