[백준/백트래킹] - N과 M 시리즈

문제 링크

N과 M (1)
N과 M (2)
N과 M (3)
N과 M (4)
N과 M (5)
N과 M (6)
N과 M (7)
N과 M (8)
N과 M (9)
N과 M (10)
N과 M (11)
N과 M (12)

N과 M (1)

조건

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 수열은 사전 순으로 증가하는 순서로 출력

코드

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

def helper(seq, cnt):
    # m개 모두 고름
    if cnt == m:
        print(*seq)
        return
    
    # 1부터 n까지의 수에 대해
    for i in range(1, n + 1):
        if i not in seq: # 고르지 않은 수라면
            helper(seq + [i], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가

helper([], 0)

---

N과 M (2)

조건

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

코드

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

def helper(prev, seq, cnt):
    # m개 모두 고름
    if cnt == m:
        print(*seq)
        return
    
    # prev는 이전에 고른 수
    # 오름차순 수열이어야 하므로, prev + 1부터 시작
    # 오름차순 수열이므로, 중복되는 수를 고르는 경우는 절대 없다. -> "if i not in prev" 필요 없음
    for i in range(prev + 1, n + 1):
        helper(i, seq + [i], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가

# 1부터 수열이 시작되므로, prev = 0
helper(0, [], 0)

---

N과 M (3)

조건

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

코드

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

def helper(seq, cnt):
    # m개 모두 고름
    if cnt == m:
        print(*seq)
        return
    
    # 1부터 n까지의 수에 대해
    for i in range(1, n + 1):
        helper(seq + [i], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가

helper([], 0)

N과 M (1)에서, 중복 확인 코드만 제거하면 된다.(같은 수를 여러 번 골라도 되므로)

---

N과 M (4)

조건

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

코드

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

def helper(prev, seq, cnt):
    # m개 모두 고름
    if cnt == m:
        print(*seq)
        return
    
    # prev는 이전에 고른 수
    # 중복 가능 & 오름차순 수열이므로 prev + 1이 아닌, prev부터 다시 시작
    for i in range(prev, n + 1):
        helper(i, seq + [i], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가

# helper내부 for문의 i는 시작값이 prev이므로
# 초기 prev = 1 이어야 수열이 1부터 시작한다.
helper(1, [], 0)

---

N과 M (5)

조건

• N개의 자연수 중에서 M개를 고른 수열
• 수열은 사전 순으로 증가하는 순서로 출력

코드

n, m = map(int, input().split())
_list = sorted(list(map(int, input().split())))

def helper(seq, cnt):
    # m개 모두 고름
    if cnt == m:
        print(*seq)
        return
    
    
    for i in range(n):
        # 중복만 제거한다.
        if _list[i] not in seq: 
            helper(seq + [_list[i]], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가

helper([], 0)

이번엔 수열을 구성할 수를 직접 입력해야 하고, 수열을 사전 순으로 증가하는 순서로 출력해야 하므로, 입력받은 수들을 list로 구성하여 sorted()를 해준다.

---

N과 M (6)

조건

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

코드

n, m = map(int, input().split())
_list = sorted(list(map(int, input().split())))

def helper(prev, seq, cnt):
    # m개 모두 고름
    if cnt == m:
        print(*seq)
        return
    
    # 오름차순 수열이므로, 중복되는 수를 고르는 경우는 절대 없다. -> "if i not in prev" 필요 없음
    # prev : 이전에 선택한 인덱스    
    for i in range(prev + 1, n):
        helper(i, seq + [_list[i]], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가

helper(-1, [], 0) # prev = -1이어야 prev + 1 = 0으로 수열을 올바르게 구성할 수 있다.

N과 M (5)에서 오름차순 수열이라는 조건이 추가됐다.
이전에 선택한 인덱스를 의미하는 prev를 추가로 사용하여, 오름차순을 만족시킨다.

---

N과 M (7)

조건

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

코드

n, m = map(int, input().split())
_list = sorted(list(map(int, input().split())))

def helper(seq, cnt):
    # m개 모두 고름
    if cnt == m:
        print(*seq)
        return
    
    for i in range(n):
        helper(seq + [_list[i]], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가

helper([], 0)

N과 M (5)에서 중복이 가능한 조건만 추가됐다. 중복 확인하는 코드를 제거하면 된다.

---

N과 M (8)

조건

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

코드

n, m = map(int, input().split())
_list = sorted(list(map(int, input().split())))

def helper(prev, seq, cnt):
    # m개 모두 고름
    if cnt == m:
        print(*seq)
        return
    
    # 중복 허용 & 오름차순을 만족시키기 위해
    # 시작 인덱스는 이전 인덱스를 의미하는 prev부터 시작한다.
    for i in range(prev, n):
        helper(i, seq + [_list[i]], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가

helper(0, [], 0)

N과 M (4)와 똑같은 문제이다. 다른 점은 직접 수들을 입력받아 List로 구성해야 한다는 것 뿐이다.

---

N과 M (9)

조건

• N개의 자연수 중에서 M개를 고른 수열
• 중복되는 수열을 여러 번 출력하면 안된다.

실패코드

n, m = map(int, input().split())
_list = sorted(list(map(int, input().split())))
total = set()

def helper(prev, seq, cnt):
    # m개 모두 고름
    if cnt == m:
        if tuple(seq) not in total:
            total.add(tuple(seq))
            # print(*seq)
        return
    
    for i in range(n):
        if prev != i:
            helper(i, seq + [_list[i]], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가

helper(-1, [], 0)

성공코드

n, m = map(int, input().split())
_list = sorted(list(map(int, input().split())))
check = [0] * n # 사용 여부를 체크하는 리스트
total = set() # 수열의 중복 제거

def helper(seq, cnt):
    # m개 모두 고름
    if cnt == m:
        total.add(tuple(seq)) # 리스트는 set에 넣을 수가 없으므로, tuple로 변환
        return
    
    for i in range(n):
        # 중복 선택 제거하기
        if not check[i]:
            check[i] = 1 # 사용 처리
            helper(seq + [_list[i]], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가
            check[i] = 0 # 사용 해제
            
helper([], 0)

# 출력
for t in sorted(total):
    print(*t)

---

N과 M (10)

조건

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.

코드

n, m = map(int, input().split())
_list = sorted(list(map(int, input().split())))
check = [0] * n # 사용 여부를 체크하는 리스트
total = set() # 수열의 중복 제거

def helper(prev, seq, cnt):
    # m개 모두 고름
    if cnt == m:
        total.add(tuple(seq)) # 리스트는 set에 넣을 수가 없으므로, tuple로 변환
        return
    
    for i in range(prev + 1, n):
        helper(i, seq + [_list[i]], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가
            
helper(-1, [], 0)

# 출력
for t in sorted(total):
    print(*t)

---

N과 M (11)

조건

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

코드

n, m = map(int, input().split())
_list = sorted(list(map(int, input().split())))
check = [0] * n # 사용 여부를 체크하는 리스트
total = set() # 수열의 중복 제거

def helper(seq, cnt):
    # m개 모두 고름
    if cnt == m:
        total.add(tuple(seq)) # 리스트는 set에 넣을 수가 없으므로, tuple로 변환
        return
    
    for i in range(n):
        helper(seq + [_list[i]], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가
            
helper([], 0)

# 출력
for t in sorted(total):
    print(*t)

---

N과 M (12)

조건

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

코드

n, m = map(int, input().split())
_list = sorted(list(map(int, input().split())))
check = [0] * n # 사용 여부를 체크하는 리스트
total = set() # 수열의 중복 제거

def helper(prev, seq, cnt):
    # m개 모두 고름
    if cnt == m:
        total.add(tuple(seq)) # 리스트는 set에 넣을 수가 없으므로, tuple로 변환
        return
    
    for i in range(prev, n):
        helper(i, seq + [_list[i]], cnt + 1) # 고른 수를 추가하고, 고른 횟수 증가
            
helper(0, [], 0)

# 출력
for t in sorted(total):
    print(*t)

---