[백준] 15651번/15652번 N과 M(3)/(4)

N과 M(3) - 15651번

문제

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.

예제 입출력

# 입력
4 2
# 출력
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

생각한 알고리즘

• 백트래킹

## 백트래킹
# 입력
N, M = map(int, input().split())

# 배열 초기화
orders = []
for i in range(M):
    orders.append(0)
# 백트랙킹 함수
def back (idx,order_list) :
    ord_list = order_list[:]
    if(idx >= M) :
        # 완성된 수열 출력
        for i in range(M-1):
            print(ord_list[i],end = " ")
        print(ord_list[M-1])
    else :
        for i in range(1,N+1):
            # 수열 생성
            ord_list[idx] = i
            back(idx+1,ord_list)

back(0,orders)

N과 M(4) - 15652번

문제

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.
  • 고른 수열은 비내림차순이어야 한다

예제 입출력

# 입력
4 2
# 출력
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

생각한 알고리즘

• 백트래킹

## 백트래킹
# 입력
N, M = map(int, input().split())

orders = []
for i in range(M):
    orders.append(0)
# 백트랙킹 함수
def back(idx,order_list):
    ord_list = order_list[:]
    if(idx >= M):
        # 완성된 수열 출력
        for i in range(M-1):
            print(ord_list[i],end = " ")
        print(ord_list[M-1])
    else:
        st = 1 if (idx == 0) else order_list[idx-1]
        for i in range(st ,N+1):
            # 이전 idx 위치의 배열 값보다 큰 값 할당
            ord_list[idx] = i
            back(idx + 1, ord_list)

back(0,orders)