공부 155일차: 백준 15652번 N과 M (4) 자바 java

15652 N과 M (4)

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

15652번: N과 M (4)

 

 

 

 

---

백준 15652번 문제 N과 M (4)

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/293

공부 154일차: 백준 15651번 N과 M (3) 자바 java

 

 

N과 M 4번째 문제 (이 문제와 유사한건 3번째)

 

 

추가된 조건은 아래와 같다

 

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

비내림차순은 즉 내림차순이 아니기만 하면 되므로,

1)같은 숫자가 반복되는 수열

2)오름차순인 수열

모두 포함한다

 

따라서 3번째 문제일 때처럼, visited[] 배열은 만들지않고 진행한다

대신 arr[]에서 이전 숫자보다 같거나 클 경우에만 넣을 수 있도록 한다

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, m;
    static int[] arr;
    static BufferedWriter bw;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        DFS(0);
        
        bw.flush();
        bw.close();
 
    }
 
    static void DFS(int depth) throws IOException{
        if(depth == m) {
            for(int num : arr) {
                bw.write(num+" ");
            }
            bw.newLine();
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(depth == 0) {    // depth-1이 -1이 되지 않도록 주는 조건
                arr[depth] = i+1;
                DFS(depth+1);
            }else{
                if(i+1 >= arr[depth-1]) {    // 같거나 크다 == 비내림차순
                arr[depth] = i+1;
                DFS(depth+1);    
                }
            }
        }
    }
}

정답 인정처리는 되었지만 if, else안에서 반복되는 코드가 있으므로 다르게 줄 방법을 찾는 것이 좋다

 

 

2)

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, m;
    static int[] arr;
    static BufferedWriter bw;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        DFS(0, 0);
        
        bw.flush();
        bw.close();
 
    }
 
    static void DFS(int start, int depth) throws IOException{
        if(depth == m) {
            for(int num : arr) {
                bw.write(num+" ");
            }
            bw.newLine();
            return;
        }
        
        for(int i = start; i < n; i++) {    // i를 매개변수 start부터
            arr[depth] = i+1;
            DFS(i, depth+1);    // 중복을 허용하도록
        }
    }
}
// 과정 https://gimbalja.tistory.com/294

찾아보니 많은 분들이 메서드에 start 숫자를 받는 방법을 사용했다

 

설명이 자세해 참고하기 좋아보이는 블로그는 https://st-lab.tistory.com/117

 

 

 

---