[파이썬] 백준 N과 M (2)

15650번: N과 M (2)

나의 풀이

• 수열이 오름차순인지 확인하기 위해서, 정렬 전후가 같은지 체크하는 방식으로 풀었다.
• 답은 맞았지만, 가능성이 없는 수열도 불필요하게 계산된다는 단점이 있다.

def get_num(k):
    # 수열이 완성된 경우
    if k == m:
        if sorted(num_list) == num_list:
            print(*num_list)
        return
    # 수열에 원소 저장
    for i in range(1, n + 1):
        if not isused[i]:
            num_list[k] = i
            isused[i] = 1
            get_num(k + 1)
            # 사용 후 제거
            isused[i] = 0
                    
def solution(n, m):
    # 숫자 중복 여부 확인
    global isused
    isused = [0] * (n + 1)
    # 현재 수열
    global num_list
    num_list = [0] * m
    get_num(0)
    
n, m = map(int, input().split())
solution(n, m)

---

• 앞서 언급한 단점을 해결하기 위해서, for문 범위를 [ic]i + 1[/ic] 부터 시작하도록 변경해 불필요한 계산을 없앴다.

def get_num(k, start):
    # 수열이 완성된 경우
    if k == m:
        if sorted(num_list) == num_list:
            print(*num_list)
        return
    # 수열에 원소 저장
    for i in range(start, n + 1):
        if not isused[i]:
            num_list[k] = i
            isused[i] = 1
            get_num(k + 1, i + 1)
            # 사용 후 제거
            isused[i] = 0
                    
def solution(n, m):
    # 숫자 중복 여부 확인
    global isused
    isused = [0] * (n + 1)
    # 현재 수열
    global num_list
    num_list = [0] * m
    get_num(0, 1)
    
n, m = map(int, input().split())
solution(n, m)