[BOJ_Python] 15649 ~ 15652. N과 M 시리즈 1 (1 ~ 4)

문제

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

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

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

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

 

사용 알고리즘

Backtracking

 

풀이

후기

1. 이 문제 시리즈는 큰 틀은 비슷하고 조건에 따라 약간의 변화를 추가한 백트레킹 문제이다.

백트레킹은 주로 들어가기 전에 해준 처리를 나와서 초기화 시키며 진행하는 방법을 사용한다.

2. 백트레킹 유형을 통해 순열과 조합 등의 방식을 직접 구현 할 수 있었다.

 

15649. N과 M (1) 

1. 이 문제가 이후 문제 풀이에 가장 기초 틀이 되는 문제이다.

2. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다.

 - 이때, 순서를 고려한 순열(Permutation)을 출력한다.

 - 때문에, 현재 리스트를 들고 다니며 다음 넣을 수가 리스트에 있는지 여부를 확인하는 if문이 필요했다.

import sys
input = sys.stdin.readline


def backtracking(N, M, lst):
    if len(lst) == M:
        print(*lst)
        return

    for i in range(1, N + 1):
        if i not in lst:
            lst.append(i)
            backtracking(N, M, lst)
            lst.pop()


N, M = map(int, input().split())
backtracking(N, M, [])

 

15650. N과 M (2) 

1. 이 문제는 1번 문제에서 순서를 고려하지 않은 문제이다.

2. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다.

 - 이때, 순서를 고려하지 않은 조합(Combination)을 출력한다.

 - 때문에, if문 대신 for문 흐름에 따라 진행을 위해 현재 기준점은 i를 들고 다니며 확인한다.

import sys
input = sys.stdin.readline


def backtracking(N, M, cur, lst):
    if len(lst) == M:
        print(*lst)
        return

    for i in range(cur, N + 1):
        lst.append(i)
        backtracking(N, M, i + 1, lst)
        lst.pop()


N, M = map(int, input().split())
backtracking(N, M, 1, [])

 

15651. N과 M (3) 

1. 이 문제는 1번 문제에서 중복을 고려하지 않은 문제이다.

2. 1부터 N까지 자연수 중에서 M개를 고른 수열을 출력한다.

 - 이때, 중복도 가능하며 순서도 고려하여 모든 가능한 순서쌍을 확인하는 데카르트 곱을 출력한다.

 - 때문에, if문 확인과 현재 기준점 i 모두 따로 확인할 필요 없이 기본 백트레킹을 진행한다.

import sys
input = sys.stdin.readline


def backtracking(N, M, lst):
    if len(lst) == M:
        print(*lst)
        return

    for i in range(1, N + 1):
        lst.append(i)
        backtracking(N, M, lst)
        lst.pop()


N, M = map(int, input().split())
backtracking(N, M, [])

 

15653. N과 M (4) 

1. 이 문제는 중복 없는 조합의 변형이다.

2. 1부터 N까지 자연수 중에서 M개를 고른 수열을 출력한다.

 - 이때, 중복은 가능하지만, 순서는 고려되지 않은 자기 자신을 포함한 조합을 출력한다.

 - 때문에, 현재 기준점은 i를 들고 다니며 백트레킹을 진행 시

   다음 i+1부터 진행이 아닌 자기자신 i 부터 다시 진행되는 점이 기존 조합과 다르다.

import sys
input = sys.stdin.readline


def backtracking(N, M, cur, lst):
    if len(lst) == M:
        print(*lst)
        return

    for i in range(cur, N + 1):
        lst.append(i)
        backtracking(N, M, i, lst)
        lst.pop()


N, M = map(int, input().split())
backtracking(N, M, 1, [])