[백준 15651번] N과 M(3) (자바)

백준알고리즘 15651번 : N과 M(3) (Solved.ac 난이도 Silver3)

 

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

15651번: N과 M (3)

 

 

배열에 값을 담은뒤에 DFS를 이용하여 출력하는 문제이다.

처음에는 출력해야하는 길이값에 따른 배열에 담지않고 바로 출력할수는 없을까.. 라고 생각해서 풀어보았다.

당연하게도 앞에서 여러번 출력되어야하는 숫자들이 한번씩만 출력된다.

요지는 배열의 길이만큼 숫자를 채울때까지 DFS를 돌리고, 다 찬 시점에 바로바로 StringBuilder에 String값을 append해야하는 것이다.

바로바로 출력시키게하면 마음은 편하겠지만 시간초과가 날 것이 예정된 수순이다.

 

풀이 과정

---

1. 자연수 N과 M, 그리고 M의 길이를 갖는 int 배열을 static 변수로 정의한다.
2. 재귀를 몇번 돌고있는지 확인할 수 있도록 현재 입력한 길이를 파라미터로 갖는
    DFS 메소드를 정의한다.
3. DFS가 M의 길이에 미치지 못했다면 int 배열에 해당 위치 index에 대한 값을 넣고,
    index를 1추가하여 다시 DFS를 돌도록 한다.
4. M의 길이에 미쳤다면 StringBuilder에 현재 배열 값을 append한다,

 

 

 

▽ 정답 소스 보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {// [Silver3] No15651 : N과 M (3)

    static int nums;
    static int len;
    static int[] arr;
    static StringBuffer sb = new StringBuffer();

    public static void main(String[] args) throws IOException {
//4 2
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        nums = Integer.parseInt(st.nextToken());
        len = Integer.parseInt(st.nextToken());
        arr = new int[len];
        DFS(0);
        System.out.println(sb.toString());

    }

    public static void DFS(int leng) {
        if (leng < len) {
            for (int i = 1; i <= nums; i++) {
                arr[leng] = i;
                DFS(leng + 1);
            }
        } else {
            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
        }
    }
}