[백준/JAVA] 15657번: N과 M (8)

🔺 문제

15657번: N과 M (8)

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] arr, ans;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new int[N];
        ans = new int[M];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
       Arrays.sort(arr); // 입력값 오름차순 정렬
        
        back(0, 0);
        System.out.println(sb);
    }
    
    private static void back(int startIdx, int cnt) {
        if(cnt == M) {
            for(int i : ans)    sb.append(i).append(" ");
            sb.append("\n");
            return;
        }
        
        // 📍 startIdx부터 처리하면 중복 수 추출 방지 & 순서가 다른 조합 추출 방지
        for(int i = startIdx ; i < N ; i++) {
            ans[cnt] = arr[i]; // ars[cnt] !!
            back(i, cnt + 1);   // 🔔 본인도 포함해야 하므로 i를 넣음
        }
    }
}

✅ 해결 아이디어
✔ 백트래킹
- 수열은 사전 순으로 증가하는 순이어야 하므로 배열을 오름차순 정렬한다. (Line 27)

 

💥 유의사항

•  Line 37 | for문

  ⇨ 인덱스를 startIdx부터 하는 이유 : 중복되는 수, 순서가 다른 조합 추출을 방지할 수 있다.

(예 : 앞에서 이미 (1,7), (1, 8), (1, 9)를 뽑았는데 인덱스를 0으로 시작하면, (8, 1), (8, 7),  (9, 1), (9, 7), (9, 8) 이런 경우도 뽑힘)

 

•  Line 39 | back(i, cnt + 1)

⇨ 본인도 포함해야 하므로 i + 1이 아닌 i를 매개 변수로 넘긴다.

  i+1으로 넘기면 (1,1) (7,7) (8,8) 같이 본인을 포함하는 경우는 만들 수 없기 때문.

 

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

이번 문제 디버깅해보고 인자 바꾸면서

왜 여기에 이 변수를 사용해야 하는지 좀 더 체감했다...

 

앞으로 복습을 더 자주해서 감을 확실히 잡자,,,

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 15657: N과 M (8)(Java)

 

[백준 15657] N과 M (8) (자바)