[BOJ][Python]N과 M

https://www.acmicpc.net/problem/15649

https://www.acmicpc.net/problem/15650

https://www.acmicpc.net/problem/15651

https://www.acmicpc.net/problem/15652

📌풀이(1)

---

내가 쓴 풀이(성공)

• backtracking 활용
• tmp: 순열의 각 경우의 수를 구현하기 위한 리스트

def backtracking(n, m, tmp = []): 
    if len(tmp) == m: # 원하는 갯수만큼 값이 있는 경우
        print(*tmp) # 출력
        return
    for num in range(1, n+1):
        if num in tmp: # 이미 들어있는 숫자인 경우, continue
            continue
        tmp.append(num) # 값 추가
        backtracking(n, m, tmp) # 다음 단계 진행
        tmp.pop() # 값 꺼냄


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

📌풀이(2)

---

내가 쓴 풀이(성공)

• (1)이 순열이었다면, (2)는 조합
• 같은 경우가 나타나지 않게 하기 위해, 시작 숫자를 설정

def backtracking(i, n, m, tmp = []):
    if len(tmp) == m: # 원하는 갯수만큼 값이 있는 경우
        print(*tmp) # 출력
        return
    for num in range(i, n+1): # 시작 숫자 i 기준
        if num in tmp: # 이미 들어있는 숫자인 경우, continue
            continue
        tmp.append(num)
        backtracking(num+1, n, m, tmp) # 다음 숫자로 진행
        tmp.pop()


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

📌풀이(3)

---

내가 쓴 풀이(성공)

• 숫자가 중복되는 경우도 고려

def backtracking(n, m, tmp = []):
    if len(tmp) == m: # 원하는 갯수만큼 값이 있는 경우
        print(*tmp) # 출력
        return
    for num in range(1, n+1): 
        tmp.append(num)
        backtracking(n, m, tmp)
        tmp.pop()


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

📌풀이(4)

---

내가 쓴 풀이(성공)

• 숫자가 중복되는 경우 고려
• 오름차순의 경우만 고려

def backtracking(i, n, m, tmp = []):
    if len(tmp) == m: # 원하는 갯수만큼 값이 있는 경우
        print(*tmp) # 출력
        return
    for num in range(i, n+1):
        tmp.append(num)
        backtracking(num, n, m, tmp)
        tmp.pop()


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

📌후기

---

백트래킹,,,아직 너무 어렵다ㅠㅠㅠ많은 연습이 필요한 것 같다! 같은 유형인데 조금씩 설정을 바꾼 문제들이라 (1)을 해결한 이후에는 빠르게 해결할 수 있었다.