[BOJ] N과 M 1~4 (no.15649~15652)

N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

🤔 생각

• itertools 를 쓰면 졸면서도 풀 수 있을 문제지만
• 백트래킹 공부 목적이니 백트래킹으로도 풀어보자.

📌 itertools 풀이

from itertools import permutations
import sys
input = sys.stdin.readline

def main():
    n,m = map(int, input().split())
    for perm in permutations(range(1,n+1),m):
        print(*perm)

if __name__ == "__main__":
    sys.exit(main())

📌 백트래킹 풀이

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
cache = [False]*n
ans = []

def solve(level):
    if level == m:
        print(*ans)
        return

    for i in range(n):
        if cache[i]: continue
        cache[i] = True
        ans.append(i+1)
        solve(level+1)
        cache[i] = False
        ans.pop()

solve(0)

---

N과 M (2)

1번 문제가 순열이라면 이건 조합을 구하는 문제다.

📌 itertools 풀이

from itertools import combinations
import sys
input = sys.stdin.readline

def main():
    n,m = map(int, input().split())
    for comb in combinations(range(1,n+1), m): print(*comb)

if __name__ == "__main__":
    sys.exit(main())

아 이러면 안되는데 자꾸 조합인게 보이니까 itertools를 쓰고 싶다..
백트래킹하자 백트래킹

📌 백트래킹 풀이

import sys
input = sys.stdin.readline

def main():
    n,m = map(int, input().split())
    ans = []
    cache = [False]*n

    def solve(level, idx):
        if level == m:
            print(*ans)
            return

        for i in range(idx, n):
            if cache[i]: continue
            cache[i] = True
            ans.append(i+1)
            solve(level+1, i)
            cache[i] = False
            ans.pop()

    solve(0,0)

if __name__ == "__main__":
    sys.exit(main())

---

N과 M (3)

이번엔 중복순열이다...

📌 itertools 풀이

from itertools import product
import sys
input = sys.stdin.readline

def solve():
    n,m = map(int, input().split())
    li = map(str, range(1,n+1))
    print("\n".join(list(map(" ".join, product(li, repeat=m)))))

if __name__ == "__main__":
    sys.exit(solve())

파이썬은 itertools를 만들지 말았어야 했다. 너무 편해서 자꾸 이것만 쓰려고 하기 때문이다..ㅋㅋㅋㅋ

📌 백트래킹 풀이

import sys
input = sys.stdin.readline

def main():
    n,m = map(int, input().split())
    ans = []

    def solve(depth):
        if depth == m:
            print(*ans)
            return

        for i in range(n):
            ans.append(i+1)
            solve(depth+1)
            ans.pop()

    solve(0)

if __name__ == "__main__":
    sys.exit(main())

---

N과 M (4)

중복조합을 구현하면 된다

📌 itertools 풀이

from itertools import combinations_with_replacement as cbr
import sys
input = sys.stdin.readline

def main():
    n,m = map(int, input().split())
    li = map(str, range(1,n+1))
    print("\n".join(map(" ".join, cbr(li,m))))

if __name__ == "__main__":
    sys.exit(main())

📌 백트래킹 풀이

import sys
input = sys.stdin.readline

def main():
    n,m = map(int, input().split())
    ans = []

    def solve(depth, idx):
        if depth == m:
            print(*ans)
            return

        for i in range(idx,n):
            ans.append(i+1)
            solve(depth+1,i)
            ans.pop()

    solve(0,0)

if __name__ == "__main__":
    sys.exit(main())

---

✔ 회고

• 백트래킹 방식이 다시 익숙해진것 같다!
• itertools 가 이런 문제에서는 거의 치트키인듯 하다..
• N과 M은 12까지 있는데, 숫자열이 연속범위냐 아니냐의 차이라 크게 어렵지 않았다!