문제

 

 

15650번: N과 M (2)

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

www.acmicpc.net

 

15651번: N과 M (3)

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

www.acmicpc.net

 

15652번: N과 M (4)

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

www.acmicpc.net

 

15654번: N과 M (5)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

 

15655번: N과 M (6)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

 

15656번: N과 M (7)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

 

15657번: N과 M (8)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

 

15663번: N과 M (9)

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

www.acmicpc.net

 

15664번: N과 M (10)

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

www.acmicpc.net

 

15665번: N과 M (11)

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

www.acmicpc.net

 

15666번: N과 M (12)

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

www.acmicpc.net

 

풀이

 

 문제의 조건에 따라 백트래킹(DFS) 함수를 변형해 풀이하면 된다. (기본 문제와 백트래킹에 대한 설명은 아래 글에서 확인할 수 있다.)

 

 

[백준] 15649번: N과 M (1) - Kotlin[코틀린]

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

code-tips.tistory.com

 

코드

 

- N과 M (2)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val visited = BooleanArray(n) // 방문 여부를 저장할 배열

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        for(i in 0 until n) {
            if(visited[i]) continue // 이미 방문한 값은 처리하지 않음
            if(depth!=0 && arr[depth - 1] > i) continue // i가 이전 숫자보다 작은 경우 처리하지 않음

            visited[i] = true
            arr[depth] = i + 1
            dfs(depth+1)
            visited[i] = false
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (3)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        for(i in 0 until n) { // 같은 숫자 선택 가능
            arr[depth] = i + 1
            dfs(depth+1)
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (4)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        for(i in 0 until n) {
            if(depth!=0 && arr[depth - 1] > i + 1) continue // i + 1이 이전 숫자보다 작은 경우 처리하지 않음
            arr[depth] = i + 1
            dfs(depth+1)
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (5)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val visited = BooleanArray(n) // 방문 여부를 저장할 배열
    val numbers = br.readLine().split(" ").map { it.toInt() }.sorted() // 숫자 리스트 생성 및 오름차순 정렬

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        for(i in 0 until n) {
            if(visited[i]) continue // 이미 방문한 값은 처리하지 않음
            //if(depth!=0 && arr[depth - 1] > numbers[i]) continue // i가 이전 숫자보다 작은 경우 처리하지 않음
            visited[i] = true
            arr[depth] = numbers[i]
            dfs(depth+1)
            visited[i] = false
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (6)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val visited = BooleanArray(n) // 방문 여부를 저장할 배열
    val numbers = br.readLine().split(" ").map { it.toInt() }.sorted() // 숫자 리스트 생성 및 오름차순 정렬

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        for(i in 0 until n) {
            if(visited[i]) continue // 이미 방문한 값은 처리하지 않음
            if(depth!=0 && arr[depth - 1] > numbers[i]) continue // numbers[i]가 이전 숫자보다 작은 경우 처리하지 않음
            visited[i] = true
            arr[depth] = numbers[i]
            dfs(depth+1)
            visited[i] = false
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (7)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val numbers = br.readLine().split(" ").map { it.toInt() }.sorted() // 숫자 리스트 생성 및 오름차순 정렬
    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        for(i in 0 until n) {
            arr[depth] = numbers[i]
            dfs(depth+1)
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (8)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val numbers = br.readLine().split(" ").map { it.toInt() }.sorted() // 숫자 리스트 생성 및 오름차순 정렬
    
    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        for(i in 0 until n) {
            if(depth!=0 && arr[depth - 1] > numbers[i]) continue // numbers[i]가 이전 숫자보다 작은 경우 처리하지 않음
            arr[depth] = numbers[i]
            dfs(depth+1)
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (9)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val visited = BooleanArray(n) // 방문 여부를 저장할 배열
    val numbers = br.readLine().split(" ").map { it.toInt() }.sorted() // 숫자 리스트 생성 및 오름차순 정렬

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        var before = 0 // 이전에 선택한 숫자를 저장하는 변수

        for(i in 0 until n) {
            if(visited[i]) continue // 이미 방문한 값은 처리하지 않음
            if(before == numbers[i]) continue // 중복된 숫자는 처리하지 않음
            visited[i] = true
            arr[depth] = numbers[i]
            before = numbers[i] // 현재 숫자를 이전 숫자로 저장
            dfs(depth+1)
            visited[i] = false
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (10)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val visited = BooleanArray(n) // 방문 여부를 저장할 배열
    val numbers = br.readLine().split(" ").map { it.toInt() }.sorted() // 숫자 리스트 생성 및 오름차순 정렬

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        var before = 0 // 이전에 선택한 숫자를 저장하는 변수

        for(i in 0 until n) {
            if(visited[i]) continue // 이미 방문한 값은 처리하지 않음
            if(before == numbers[i]) continue // 중복된 숫자는 처리하지 않음
            if(depth!=0 && arr[depth - 1] > numbers[i]) continue // numbers[i]가 이전 숫자보다 작은 경우 처리하지 않음
            visited[i] = true
            arr[depth] = numbers[i]
            before = numbers[i] // 현재 숫자를 이전 숫자로 저장
            dfs(depth+1)
            visited[i] = false
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (11)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val numbers = br.readLine().split(" ").map { it.toInt() }.sorted() // 숫자 리스트 생성 및 오름차순 정렬

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        var before = 0 // 이전에 선택한 숫자를 저장하는 변수

        for(i in 0 until n) {
            if(before == numbers[i]) continue // 중복된 숫자는 처리하지 않음
            arr[depth] = numbers[i]
            before = numbers[i] // 현재 숫자를 이전 숫자로 저장
            dfs(depth+1)
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

- N과 M (12)

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val numbers = br.readLine().split(" ").map { it.toInt() }.sorted() // 숫자 리스트 생성 및 오름차순 정렬

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach { sb.append("$it ") }
            sb.append("\n")
            return
        }

        var before = 0 // 이전에 선택한 숫자를 저장하는 변수

        for(i in 0 until n) {
            if(before == numbers[i]) continue // 중복된 숫자는 처리하지 않음
            if(depth!=0 && arr[depth - 1] > numbers[i]) continue // numbers[i]가 이전 숫자보다 작은 경우 처리하지 않음
            arr[depth] = numbers[i]
            before = numbers[i] // 현재 숫자를 이전 숫자로 저장
            dfs(depth+1)
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

 

'알고리즘 > Baekjoon' 카테고리의 다른 글

[백준] 1018번: 체스판 다시 칠하기 - Kotlin[코틀린]  (0) 2023.10.04
[백준] 1193번: 분수찾기 - Kotlin[코틀린]  (0) 2023.09.30
[백준] 15649번: N과 M (1) - Kotlin[코틀린]  (0) 2023.09.28
[백준] 1890번: 점프 - Kotlin[코틀린]  (0) 2023.09.27
[백준] 7576번: 토마토 - Kotlin[코틀린]  (0) 2023.09.27

티스토리툴바