BJ S1 15651 N과M(3) - Java

[문제링크]

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

---

[문제]

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

---

[입력]

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

---

[출력]

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

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

---

[예제 입력 1]

3 1

---

[예제 출력 1]

1
2
3

---

[예제 입력 2]

4 2

---

[예제 출력 2]

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

---

[설명]

이 문제는 다른 N과M 문제와 마찬가지로 백트래킹 문제이다.N과M(2)와 다른 점은 앞의 수와 겹쳐도 된다는 점이다. 때문에 visited 변수는 사용하지 않았다.여기서 문제가 발생했는데, visited 없이 답안을 작성해서 풀었을 때, 예시의 답변에는 잘 동작하였다.하지만 문제를 제출했을 때 시간초과가 발생했는데, 알고보니 아주 작은 차이로 시간초과가 걸리는 것이었다..!

 

Java 코딩테스트를 하면서 시간초과가 걸리는 경우를 간혹 볼 수 있는데, 이럴 때는 출력이나 입력을 한번에 정리해서 받으면 해결되는 경우가 존재한다!따라서 System.out.print() 대신 StringBuilder를 이용해 출력할 값들을 한번에 StringBuilder에 저장한 뒤, 마지막에 stringBuilder만 출력하도록 설정하니 문제의 정답을 맞출 수 있었다.

백준 알고리즘 15651번 JAVA풀이

 

import java.util.*;

public class BJ15651 {

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[M];

        backtracking(arr, N, M, 0);
        System.out.println(sb);
    }

    static void backtracking(int[] arr, int N, int M, int depth){
        if(depth == M){
            for(int i=0;i<M;i++){
                sb.append(arr[i]+" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=1;i<=N;i++){
            arr[depth]=i;
            backtracking(arr, N, M, depth+1);
        }
    }
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.