BOJ(백준) 15649[N과 M (1)], 15650[N과 M (2)]

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 15649번과 15650번을 풀어보겠습니다. 이 문제들은 주어진 숫자들을 조합하여 특정 조건을 만족하는 수열을 찾는 문제입니다. 각 문제를 자세히 살펴보고, Python 코드를 통해 해결해보겠습니다.

 

1. 문제 설명

 

15649번: N과 M (1)

 

주어진 숫자 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제입니다.

문제 URL : https://www.acmicpc.net/problem/15649

 

15650번: N과 M (2)

 

주어진 숫자 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하되, 수열은 오름차순이어야 합니다.

문제 URL : https://www.acmicpc.net/problem/15650

 

 

2. 접근법

공통 접근법

1. 입력받기: N과 M을 입력받습니다.

2. 백트래킹: 재귀 함수를 이용하여 수열을 생성합니다.

3. 조건 체크: 중복이 없도록 하거나 오름차순이 되도록 조건을 추가합니다.

 

3. 정답 코드

15649번 정답 코드

import sys
input = sys.stdin.readline

# N과 M을 입력받는다. N은 1부터 N까지의 숫자, M은 수열의 길이
N, M = map(int, input().split())
arr = []  # 수열을 저장할 리스트

def rec(idx):
    # 현재 수열의 길이가 M과 같으면 출력하고 종료
    if idx == M:
        print(*arr)  # 리스트를 언팩하여 출력
        return

    # 1부터 N까지의 숫자를 차례대로 검사
    for i in range(1, N+1):
        if i not in arr:    # 현재 숫자가 수열에 포함되어 있지 않으면
            arr.append(i)   # 숫자를 수열에 추가
            rec(idx+1)      # 재귀 호출로 다음 인덱스로 이동
            arr.pop()       # 재귀 호출이 끝난 후 마지막 숫자를 제거 (백트래킹)

# 재귀 함수 호출 시작, 처음 인덱스는 0
rec(0)

 

15650번 정답 코드

import sys
input = sys.stdin.readline

# N과 M을 입력받는다. N은 1부터 N까지의 숫자, M은 수열의 길이
N, M = map(int, input().split())
arr = []  # 수열을 저장할 리스트

def rec(idx, num):
    # 현재 수열의 길이가 M과 같으면 출력하고 종료
    if idx == M:
        print(*arr)  # 리스트를 언팩하여 출력
        return
    
    # num+1부터 N까지의 숫자를 차례대로 검사
    for i in range(num+1, N+1):
        if i not in arr:    # 현재 숫자가 수열에 포함되어 있지 않으면
            arr.append(i)   # 숫자를 수열에 추가
            rec(idx+1, i)   # 재귀 호출로 다음 인덱스로 이동하고 현재 숫자를 넘겨줌
            arr.pop()       # 재귀 호출이 끝난 후 마지막 숫자를 제거 (백트래킹)

# 재귀 함수 호출 시작, 처음 인덱스는 0, 시작 숫자는 0
rec(0, 0)

 

4. 코드 설명

15649번

1. 입력받기: N과 M을 입력받아 수열의 길이와 사용할 수 있는 숫자의 범위를 설정합니다.

2. 재귀 함수 정의: 재귀 함수를 사용하여 현재 수열의 길이를 나타내는 idx를 매개변수로 받습니다.

3. 기저 조건: idx가 M과 같으면 현재 수열을 출력합니다.

4. 백트래킹: 1부터 N까지의 숫자를 검사하여, 현재 수열에 포함되지 않은 숫자를 추가하고 재귀 호출합니다. 호출이 끝나면 마지막 숫자를 제거하여 이전 상태로 되돌립니다.

 

15650번

1. 입력받기: N과 M을 입력받아 수열의 길이와 사용할 수 있는 숫자의 범위를 설정합니다.

2. 재귀 함수 정의: 재귀 함수를 사용하여 현재 수열의 길이를 나타내는 idx와 마지막으로 사용된 숫자를 나타내는 num을 매개변수로 받습니다.

3. 기저 조건: idx가 M과 같으면 현재 수열을 출력합니다.

4. 백트래킹: num+1부터 N까지의 숫자를 검사하여, 현재 수열에 포함되지 않은 숫자를 추가하고 재귀 호출합니다. 호출이 끝나면 마지막 숫자를 제거하여 이전 상태로 되돌립니다.

 

5. Github으로 확인

15649번

 

coTest/BOJ/BOJ01_04_01_15649.py at main · pcy4196/coTest

 

15650번

coTest/BOJ at main · pcy4196/coTest