[백준] 15652번 N과 M(4)

사용 언어 - Python3

15652번: N과 M(4) (실버3, DFS 백트래킹 문제)

문제 ★LG CNS 21년 상반기 코테랑 유사★

15652번: N과 M (4)

 

정답

DFS 백트래킹 재귀함수 조합 문제 !! 15649,15450,15651,15652번은 세트로 공부

• 아래 백트래킹 문제 링크를 첨부합니다.

15450번과 15652번을 적절히 조합하는 문제이다. 중복을 제거하는 if문을 없애고, start 지점을 활용한다.

현재 i가 ans에 있을 때, i부터 N까지를 for문으로 차례대로 append하게 하는 구조이다.

처음 시작점은 1로 지정해주면 1은 1부터 4까지, 2는 2부터 4까지, 3은 3부터 4까지, 4는 4와 엮여서 ana에 저장된다.

# 정답
N, M = map(int,input().split())
ans = []

def back(start):
	if len(ans) == M:
    	print(" ".join(map(str,ans)))
        return
    for i in range(start,N+1):
    	ans.append(start)
        back(start)
        ans.pop()
        
back(1)

 

---

레퍼런스

• 백준 백트래킹 15649,15450,15651,15652번은 세트로 공부해야한다.

백트래킹 문제 비교

• 15649번 중복X 수열
• 15650번 중복X 시작포인트 지정 수열
• 15651번 중복O 수열
• 15652번 중복O 시작포인트 지정 수열

 

• 15649번 [1 2] [1 3] [1 4] [2 1] [2 3] [2 4] [3 1] [3 2] [3 4] [4 1] [4 2] [4 3]
• 15650번 [1 2] [1 3] [1 4] [2 3] [2 4] [3 4]
• 15651번 [1 1] [1 2] [1 3] [1 4] [2 1] [2 2] [2 3] [2 4] [3 1] [3 2] [3 3] [3 4] [4 1] [4 2] [4 3] [4 4]
• 16652번 [1 1] [1 2] [1 3] [1 4] [2 2] [2 3] [2 4] [3 3] [3 4] [4 4]

백트래킹 단계

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부