Kim Jisong

I am an amazing person.

백준시리즈: N과 M

Introduction

재귀 함수를 연습하기 좋은 문제

백트래킹

https://www.acmicpc.net/workbook/view/2052

N과 M (1)

import sys
input = sys.stdin.readline

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):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
dfs()

N과 M (2)

import sys
input = sys.stdin.readline

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):
        if len(s) == 0 or i > s[-1]:
            s.append(i)
            dfs()
            s.pop()
dfs()

N과 M (3)

import sys
input = sys.stdin.readline

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):
        # if len(s) == 0 or i > s[-1]:
        s.append(i)
        dfs()
        s.pop()
dfs()

N과 M (4)

import sys
input = sys.stdin.readline

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):
        if len(s) == 0 or i >= s[-1]:
            s.append(i)
            dfs()
            s.pop()
dfs()

N과 M (5)

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
lists = list(map(int,input().split()))
lists.sort()

s = []

def dfs():
    if len(s) == m:
        print(" ".join(map(str,s)))
        return
    for i in range(n):
        if lists[i] not in s:
            s.append(lists[i])
            dfs()
            s.pop()
dfs()

N과 M (6)

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
lists = list(map(int,input().split()))
lists.sort()

s = []

def dfs():
    if len(s) == m:
        print(" ".join(map(str,s)))
        return
    for i in range(n):
        if lists[i] not in s:
            s.append(lists[i])
            dfs()
            s.pop()
dfs()

N과 M (7)

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
lists = list(map(int,input().split()))
lists.sort()

s = []

def dfs():
    if len(s) == m:
        print(" ".join(map(str,s)))
        return
    for i in range(n):
        if len(s) == 0 or lists[i] > s[-1]:
            s.append(lists[i])
            dfs()
            s.pop()
dfs()

N과 M (8)

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
lists = list(map(int,input().split()))
lists.sort()

s = []

def dfs():
    if len(s) == m:
        print(" ".join(map(str,s)))
        return
    for i in range(n):
        if len(s) == 0 or lists[i] > s[-1]:
            s.append(lists[i])
            dfs()
            s.pop()
dfs()

N과 M (9)

해당 문제에서 list는 정렬되어 있기 때문에 [1,7,9,9] 일 경우, 직전 값을 저장해서 같지 않을 경우만 확인하면 된다.

또한, 방문했던 값은 다시 방문해서는 안 된다. 따라서 visited 변수를 사용하여 방문했던 곳을 저장해야한다.

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
lists = list(map(int,input().split()))
lists.sort()

s = []
visited  = [False]*(n)
def dfs():
    if len(s) == m:
        print(" ".join(map(str,s)))
        return
    x = 0
    for i in range(n):
        if visited[i] == False and x != lists[i]:
            visited[i] = True
            s.append(lists[i])
            x = lists[i]
            dfs()
            s.pop()
            visited[i] = False
dfs()

N과 M (10)

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
lists = list(map(int,input().split()))
lists.sort()

s = []
visited  = [False]*(n)
def dfs():
    if len(s) == m:
        print(" ".join(map(str,s)))
        return
    x = 0
    for i in range(n):
        if visited[i] == False and x != lists[i] and (len(s)==0 or lists[i] >= s[-1]):
            visited[i] = True
            s.append(lists[i])
            x = lists[i]
            dfs()
            s.pop()
            visited[i] = False
dfs()

N과 M (11)

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
lists = list(map(int,input().split()))
lists.sort()

s = []
def dfs():
    if len(s) == m:
        print(" ".join(map(str,s)))
        return
    x = 0
    for i in range(n):
        if x != lists[i]:
            s.append(lists[i])
            x = lists[i]
            dfs()
            s.pop()
dfs()

N과 M (12)

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
lists = list(map(int,input().split()))
lists.sort()

s = []
def dfs():
    if len(s) == m:
        print(" ".join(map(str,s)))
        return
    x = 0
    for i in range(n):
        if x != lists[i] and (len(s) == 0 or lists[i] >= s[-1]):
            s.append(lists[i])
            x = lists[i]
            dfs()
            s.pop()
dfs()

2022

Stack

less than 1 minute read

Introduction

Stack

less than 1 minute read

Introduction

Download-only-one-directory

less than 1 minute read

Git 명령어를 사용한 하위 디렉토리 다운로드 Clone 할 로컬 저장소 생성

Sort

3 minute read

Introduction

Tree

less than 1 minute read

Introduction

Mutex library on C++

less than 1 minute read

#include <iostream> #include <thread> #include <chrono> #include <mutex> #include <atomic> #include <string.h>

TODO

less than 1 minute read

how to costom github blog using jekyll

Welcome to Jekyll!

less than 1 minute read

You’ll find this post in your _posts directory. Go ahead and edit it and re-build the site to see your changes. You can rebuild the site in many different wa...

Back to top ↑