BOJ(N과M)(2-12)

작성일 | In

목차

  1. N과 M(2)
  2. N과 M(3)
  3. N과 M(4)
  4. N과 M(5)
  5. N과 M(6)
  6. N과 M(7)
  7. N과 M(9)
  8. N과 M(10)
  9. N과 M(11)
  10. N과 M(12)
  • (1)은 순열 (2)는 조합을 구하는 문제였다.
  • (3)은 중복순열, (4)는 중복조합 문제다
  • (5)는 입력값을 받는 순열문제, (6)은 입력값을 받는 조합문제
  • (7) 입력 값을 받는 중복 순열문제, (8)은 입력값을 받는 중복 조합문제
  • (9) (5)의 중복 순열 문제에서, 입력값에 중복된 값이 있는 경우의 순열을 구하는 문제
  • (10) (6)의 중복조합에서 입력값에 중복된 값이 있는 경우의 조합을 구하는 문제
  • (11) (7)의 중복 순열문제에서, 입력값에 중복된 값이 있는 경우의 순열 구하기
  • (12) (8)의 중복 순열 문제에서, 입력값에 중복된 값이 있는 경우의 조합 구하기

2. 15650번 N과 M(2)

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

  • 고른 순열은 오름차순이어야 한다.

  • N과 M(1)과 달라진 조건은 오름차순이라는 말 뿐이다.
  • 예제의 출력을 확인해보면, 이전이 permutation을 이용해서 구할 수도 있는, 순열이었다면 이번 문제는 조합이라는 것을 확인할 수 있다.

  • combinations를 사용하면 쉽게 구현할 수 있겠지만, 재귀로 구현하겠다.

  • 결국 답을 못찾다가 힌트를 얻었다.
  • 평소에 계속 구현하던 거였는데, 이번에 확실히 알았다.
  • 생각해보니, 조합을 구했던 적이 있다. 바로 로또를 구했을 때였다.
def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(result))
        return
    for i in range(s, N+1):
        if str(i) not in result:
            result += str(i)
            DFS(i)
            result = result[:-1]

N, M = map(int, input().split())
result = ""
DFS(1)

3 15651번 N과 M(3)

  • N과M(1)번 문제에서 if str(i) not in result 조건을 지워주면 된다.
def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(result))
        return
    for i in range(1, N+1):
        # if str(i) not in result:
        result += str(i)
        DFS(i)
        result = result[:-1]

N, M = map(int, input().split())
result = ""
DFS(1)

4. 15652번 N과 M(4)

  • 간단하다. N과M(2)번 문제에서 if str(i) not in result 조건을 지워주면 된다.
def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(result))
        return
    for i in range(s, N+1):
        # if str(i) not in result:
        result += str(i)
        DFS(i)
        result = result[:-1]
N, M = map(int, input().split())
result = ""
DFS(1)

5. 15654번 N과 M(5)

def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(map(str, result)))
        return
    for i in range(N):
        if arr[i] not in result:
            result.append(arr[i])
            DFS(i)
            result = result[:-1]


N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())))
result = []
DFS(0)

6. 15655번 N과 M(6)

def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(map(str, result)))
        return
    for i in range(s, N):
        if arr[i] not in result:
            result.append(arr[i])
            DFS(i)
            result = result[:-1]
N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())))
result = []
DFS(0)

7. N과 M(7)

def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(map(str, result)))
        return
    for i in range(N):
        result.append(arr[i])
        DFS(i)
        result = result[:-1]
N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())))
result = []
DFS(0)

8. N과 M(8)

def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(map(str, result)))
        return
    for i in range(s, N):
        result.append(arr[i])
        DFS(i)
        result = result[:-1]


N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())))
result = []
DFS(0)

N과 M(9)

  • 9번 어렵다.
  • 핵심은 중복되는 수열을 여러분 출력하면 안된다는 것이다.
  • 값이 곧 인덱스인 checked 배열을 만들어 주어 중복을 제거한다.
  • visited 배열은 재귀적으로 완전탐색을 위한 용도이며
  • checked 배열은 재귀 함수 내에서의 중복을 피하기 위한 용도이다.
  • 그냥 input() 쓰면 시간 초과 뜨니까, import sys 해야한다.
from sys import stdin, stdout
input = stdin.readline


def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(map(str, result)))
        return
    checked = [False]*(10001)
    for i in range(N):
        if not visited[i] and not checked[arr[i]]:
            visited[i] = True
            checked[arr[i]] = True
            result.append(arr[i])
            DFS(i)
            result = result[:-1]
            visited[i] = False


N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())))
visited = [False]*(N+1)
result = []
DFS(0)

N과 M(10)


from sys import stdin
input = stdin.readline


def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(map(str, result)))
        return
    checked = [False]*(10001)
    for i in range(s, N):
        if not visited[i] and not checked[arr[i]]:
            visited[i] = True
            checked[arr[i]] = True
            result.append(arr[i])
            DFS(i)
            result = result[:-1]
            visited[i] = False


N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())))
visited = [False]*(N+1)
result = []
DFS(0)

N과 M(11)


from sys import stdin
input = stdin.readline


def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(map(str, result)))
        return
    checked = [False]*(10001)
    for i in range(N):
        if not checked[arr[i]]:
            visited[i] = True
            checked[arr[i]] = True
            result.append(arr[i])
            DFS(i)
            result = result[:-1]
            visited[i] = False


N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())))
visited = [False]*(N+1)
result = []
DFS(0)

N과 M(12)


from sys import stdin
input = stdin.readline


def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(map(str, result)))
        return
    checked = [False]*(10001)
    for i in range(s, N):
        if not checked[arr[i]]:
            visited[i] = True
            checked[arr[i]] = True
            result.append(arr[i])
            DFS(i)
            result = result[:-1]
            visited[i] = False

N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())))
visited = [False]*(N+1)
result = []
DFS(0)

참고자료

0%