[BOJ] 15650번: N과 M (2)

2022. 4. 19. 20:02· BOJ 백준/백트래킹
목차
  1. 문제
  2. 입력
  3. 출력
  4. 풀이
  5. 코드
  6. 결과
728x90
반응형

https://www.acmicpc.net/problem/15650

 

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  ▪ 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  ▪ 고른 수열은 오름차순이어야 한다.

 

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 


풀이

📘 백트래킹

 

dfs와 유사한 알고리즘이다. 차이점은 어떤 노드가 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 이전 노드(부모노드)로 돌아가 다음 자식 노드로 가서 탐색한다.

이 문제에서는 똑같은 수가 다시 나올 수 없으므로 visit 배열을 만들어서 다음 노드를 방문하기 전에는 1로 설정해놓고 다음 노드를 방문하고 나오면 0으로 설정한다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int visit[9] = {0,};
int cnt = 0;
int arr[9] = {0,};

void dfs(int a, int t) {
  if(t == m) {
    for(int i = 0; i < m; i++) {
      cout << arr[i] << " ";
    }
    
    cout << "\n";
    return;
  }

  for(int i = a; i <= n; i++) {
      visit[i] = 1;
      arr[t] = i;
      dfs(i+1, t+1);
      visit[i] = 0;
  }
}

int main() {
  cin >> n >> m;
  dfs(1, 0);
}

 

 

결과

728x90
반응형

'BOJ 백준 > 백트래킹' 카테고리의 다른 글

[BOJ] 15664번: N과 M (10)  (0) 2022.08.20
  1. 문제
  2. 입력
  3. 출력
  4. 풀이
  5. 코드
  6. 결과
'BOJ 백준/백트래킹' 카테고리의 다른 글
  • [BOJ] 15664번: N과 M (10)
코블리_vv
코블리_vv
코블리_vv
코딩 놀이터
코블리_vv
전체
오늘
어제
  • 분류 전체보기 (67)
    • CS 노트 (1)
    • 대외활동 (0)
      • 창업 동아리 (0)
    • AWS (0)
      • AWS Academy Cloud Architect.. (0)
      • AWS Lab (0)
    • 웹 개발 노트 (3)
      • 웹 프로젝트 (0)
      • 스프링 인 액션 (0)
      • 스프링 입문을 위한 자바 객체 지향의 원리와 이해 (0)
    • ORACLE (0)
    • TOPCIT (2)
      • M1 소프트웨어 개발 (2)
      • M2 데이터 이해와 활용 (0)
    • 캡스톤 (5)
    • BOJ 백준 (53)
      • 브루트포스 (1)
      • 정렬 (6)
      • 이분탐색 (5)
      • 맵 (2)
      • 다이나믹 프로그래밍 (11)
      • 수학 (5)
      • 그리디 (3)
      • 분할정복 (4)
      • DFS (3)
      • BFS (6)
      • 그래프 (4)
      • 자료구조 (1)
      • 백트래킹 (2)
    • 코딩 테스트 (0)
      • 코드트리 (0)
    • 대회 (0)
    • Spring Boot (3)
      • JPA (3)

블로그 메뉴

  • 홈
  • 태그
  • 알고리즘
  • BOJ 백준
  • 방명록

공지사항

인기 글

태그

  • 재귀
  • 투자
  • 파이썬 backtrader
  • 너비우선탐색
  • 우선순위 큐
  • 다이나믹프로그래밍
  • dp
  • n과m
  • 웹개발
  • 스프링인액션
  • java
  • 백트래킹
  • 컴퓨터 보안
  • 투자 전략
  • 1676
  • computer security
  • spring
  • binary search
  • 분할정복
  • 백준 토마토
  • dfs
  • 이분탐색
  • 다이나믹 프로그래밍
  • 플로이드 와샬
  • 시스템 트레이딩
  • 백준 n과m
  • 그리디 알고리즘
  • 암호학
  • BFS
  • backtrader

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
코블리_vv
[BOJ] 15650번: N과 M (2)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.