Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] N과 M (3), (4)
백준 15649 N과 M(3)
해결 방식
백트랙킹 : 해를 찾는 도중 해가 아니라면 다시 돌아가 해를 찾아가는 기법
dfs를 적용하는 알고리즘 방식-
해를 찾는 도중 지금 선택한 경로가 해가 되지 않는다면 해당 경로는 더 이상 돌지 않는다.
→
가지 치기방식 - 가지치기를 얼마나 잘하느냐에 따라 효율성 결정
문제
자연수 N과 M이 주어졌을 때 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
입력
- 첫 번째 줄: N, M
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.
중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
코드
n, m = map(int, input().split())
s = []
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n+1):
s.append(i)
dfs()
s.pop()
dfs()
백준 15649 N과 M(4)
문제
자연수 N과 M이 주어졌을 때 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
입력
- 첫 번째 줄: N, M
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.
중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
코드
n, m = map(int, input().split())
s = []
def dfs(start):
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(start, n+1):
s.append(i)
dfs(i)
s.pop()
dfs(1)
