BOJ

[실버 3] 15649번: N과 M (1)

2022. 9. 20. 00:04
목차
  1. 문제
  2. 입력
  3. 출력
  4. 사고의 흐름
  5. 내가 작성한 소스코드
  6. 남이 작성한 소스코드
  7. 피드백
728x90

Original Source: https://www.acmicpc.net/problem/15649

 

15649번: N과 M (1)

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

www.acmicpc.net


문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

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


사고의 흐름

더보기
  • 순열이니까 원래대로라면 itertools 라이브러리를 쓰겠지만, 지금은 Backtracking을 연습 중이니까 재귀 함수로 코드를 작성해보자.
  • 중복을 허용하지 않고 선택하려면 그냥 BFS 돌릴 때처럼 별도로 bool 타입 List를 만들면 되는구나.

내가 작성한 소스코드

import sys
r = sys.stdin.readline


def print_seqs(n, m, seq, visited, depth):
    if depth == m:
        for v in seq:
            print(v, end=" ")
        print()
        return

    for i in range(n):
        if visited[i+1] == True:
            continue
        
        seq.append(i+1)
        visited[i+1] = True
        print_seqs(n, m, seq, visited, depth+1)
        del seq[-1]
        visited[i+1] = False


n, m = map(int, r().split())
visited = [False] * (n+1)
print_seqs(n, m, [], visited, 0)

남이 작성한 소스코드

BaaaaaaaarkingDog 님:
https://blog.encrypted.gg/945

피드백

  • 조건에 따라 List 내의 원소를 선택하려면 반복문 안에서 뭔가를 하려 하지 말고, bool 타입 List를 하나 만들어서 선택할지 말지를 결정하는 정보를 저장한다.
저작자표시 (새창열림)

'BOJ' 카테고리의 다른 글

[실버 3] 15651번: N과 M (3)  (0) 2022.09.20
[실버 3] 15650번: N과 M (2)  (1) 2022.09.20
[골드 4] 14502번: 연구소  (0) 2022.09.19
[골드 4] 1261번: 알고스팟  (0) 2022.09.16
[실버 2] 3085번: 사탕 게임  (0) 2022.09.15
  • 문제
  • 입력
  • 출력
  • 사고의 흐름
  • 내가 작성한 소스코드
  • 남이 작성한 소스코드
  • 피드백
'BOJ' 카테고리의 다른 글
  • [실버 3] 15651번: N과 M (3)
  • [실버 3] 15650번: N과 M (2)
  • [골드 4] 14502번: 연구소
  • [골드 4] 1261번: 알고스팟
Park Joonyoung
Park Joonyoung
개발 블로그
DevJoon개발 블로그
Park Joonyoung
DevJoon
Park Joonyoung
전체
오늘
어제
  • 분류 전체보기 (88)
    • BOJ (41)
      • 틀렸습니다 (6)
    • 알고리즘 (4)
    • C++ (2)
    • Python (1)
    • 토이 프로젝트 (0)
    • 선형대수학 (1)
    • 기타 (3)
    • 에세이 (4)
    • [개인 보관용] (32)
      • 이코테 강의 정리 (0)
      • 알고리즘(old) (0)
      • 단변수미적분학 (0)
      • 다변수미적분학 (0)
      • 선형대수학 (32)
      • 선형대수학(old) (0)
      • 프랑스어 (0)
      • 독서노트 (0)
      • 사진 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 알고리즘
  • 선형대수학
  • 브루트포스
  • github
  • dfs
  • Notion
  • git bash
  • 그리디
  • BOJ
  • 시뮬레이션
  • It
  • 백준
  • DP
  • stl
  • bfs
  • 코딩테스트
  • 백트래킹
  • ps
  • next_permutation
  • 에세이
  • Python
  • c++
  • 구현
  • 개발
  • DevJoon
  • 수학

최근 댓글

최근 글

hELLO · Designed By 정상우.
Park Joonyoung
[실버 3] 15649번: N과 M (1)
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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