백준 N과 M 3~12 (파이썬)

1. N과 M (3)

---

1.1.1. 코드

import sys

def solve(depth, N, M):
    # depth가 M과 같아질 때 리턴
    if depth == M:
        print(*ans)
        return
    for i in range(1, N+1):
        # if visited[i]:
        #     continue
        # visited[i] = 1
        ans.append(i)
        solve(depth+1, N, M)
        # 리턴 후 실행될 코드
        # for문이 끝나도 실행이 된다.
        ans.pop()
        visited[i] = 0



N, M = map(int, sys.stdin.readline().split())
arr = []
for i in range(1, N+1):
    arr.append(i)

visited = [0] * (N+1)
ans = []
solve(0, N, M)PYTHON

---

1.1.2. comment

• N과 M (1) 이 중복 없이 수열을 출력하는 것이면, 이번 문제는 중복이 가능하다.
• 따라서, visited라는 조건문을 없애주면 쉽게 풀 수 있다.

---

2. N과 M (4)

---

2.1.1. 코드

import sys

def solve(depth, N, M):
    # depth가 M과 같아질 때 리턴
    if depth == M:
        print(*ans)
        return
    for i in range(1, N+1):
        # if visited[i]:
        #     continue
        if not ans:
            # visited[i] = 1
            ans.append(i)
            solve(depth + 1, N, M)
            ans.pop()
            visited[i] = 0
        elif i >= ans[-1]:
            # visited[i] = 1
            ans.append(i)
            solve(depth+1, N, M)
            ans.pop()
            visited[i] = 0




N, M = map(int, sys.stdin.readline().split())
arr = []
for i in range(1, N+1):
    arr.append(i)

visited = [0] * (N+1)
ans = []
solve(0, N, M)PYTHON

---

2.1.2. comment

• N과 M (2)번 문제를 조금만 수정하면 된다.
• 일단, 중복이 가능하니 visited를 빼준다.
• 그 후, 2 번의 경우에는 다음에 넣어줄 숫자가 자신보다 크면이었지만, 이 조건을
• 자신보다 크거나 같으면 으로 바꿔주면 된다.

---

3. N과 M (5)

---

3.1.1. 코드

import sys

def solve(depth, N, M):
    if depth == M:
        print(*ans)
        return
    for i in arr:
        if visited[i]:
            continue
        visited[i] = 1
        ans.append(i)
        solve(depth+1, N, M)
        # return후 할 작업
        ans.pop()
        visited[i] = 0



N, M = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
max_arr = max(arr)
visited = [0] * (max_arr+1)
ans = []

solve(0, N, M)PYTHON

---

3.1.2. comment

• N과 M 1번 문제를 조금 수정하면 된다.
• for문이 도는걸 list로 받은 arr로 돌게 해주면 된다.

---

4. N과 M (6)

---

4.1.1. 코드

import sys

def solve(depth, N, M):
    if depth == M:
        print(*ans)
        return
    for i in arr:
        if visited[i]:
            continue
        if not ans:
            visited[i] = 1
            ans.append(i)
            solve(depth+1, N, M)
            ans.pop()
            visited[i] = 0
        elif i > ans[-1]:
            visited[i] = 1
            ans.append(i)
            solve(depth+1, N, M)
            ans.pop()
            visited[i] = 0



N, M = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
max_arr = max(arr)
visited = [0] * (max_arr+1)
ans = []

solve(0, N, M)PYTHON

---

4.1.2. comment

• N과 M (2)에서 약간 수정해주면 된다.
• for문을 arr로 순회하게 해주면 된다.

---

5. N과 M (7)

---

5.1.1. 코드

import sys

def solve(depth, N, M):
    if depth==M:
        print(*ans)
        return
    for i in arr:
        ans.append(i)
        solve(depth+1, N, M)
        ans.pop()





N, M = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
max_arr = max(arr)
visited = [0] * (max_arr+1)
ans = []

solve(0, N, M)PYTHON

---

5.1.2. comment

• 그냥 visited없애주고 arr에서 for문이 돌게 하면 된다.

---

6. N과 M (8)

---

6.1.1. 코드

import sys

def solve(depth, N, M):
    if depth==M:
        print(*ans)
        return
    for i in arr:
        if not ans:
            ans.append(i)
            solve(depth + 1, N, M)
            ans.pop()
        elif i >= ans[-1]:
            ans.append(i)
            solve(depth+1, N, M)
            ans.pop()

N, M = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
max_arr = max(arr)
visited = [0] * (max_arr+1)
ans = []

solve(0, N, M)PYTHON

---

6.1.2. comment

• 전의 문제에서 조건을 i>=ans[-1]을 걸어주면 된다.

---

7. N과 M (9)

---

7.1.1. 코드

import sys

def solve(depth, N, M):
    if depth==M:
        print(*ans)
        return
    # 현재 저장하고 있는 값을 표현, 중복 제거
    tmp = 0
    # 이 문제는 인덱스를 for문에 사용해야 한다.
    for i in range(len(arr)):
        # 방문했거나, tmp가 현재의 값과 같으면 continue
        if visited[i] or tmp == arr[i]:
            continue
        visited[i] = 1
        ans.append(arr[i])
        tmp = arr[i]
        solve(depth + 1, N, M)
        val = ans.pop()
        visited[i] = 0


N, M = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
# 인덱스를 visited에 사용할 것이므로 N만큼 visited를 설정
visited = [0] * N
ans = []
solve(0, N, M)PYTHON

---

7.1.2. comment

• 조금 시간이 걸렸다.
• 뒤의 값이 중복 되면 안되기 때문에 tmp라는 변수를 설정해줬다.
• 이 문제의 경우 for문을 순회하는 것을 인덱스로 접근해야한다.
• 왜냐면, 9 9를 출력해야 하는 상황인데, 그냥 arr의 값으로 for문을 순회하면,
• visited[9]가 방문 처리 되어있어서, 중복이라고 판단해버린다.