[코드트리 조별과제] 특정 조건에 맞게 k개 중에 1개를 n번 뽑기 (백트레킹, 자바)

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제

1이상 K이하의 숫자를 하나 고르는 행위를 N번 반복하여 나올 수 있는 모든 서로 다른 순서쌍을 구해주는 프로그램을 작성해보세요. 단, 연속하여 같은 숫자가 3번 이상 나오는 경우는 제외합니다.

예를 들어 K이 2, N이 3인 경우 다음과 같이 6개의 조합이 가능합니다.

1 1 2

1 2 1

1 2 2

2 1 1

2 1 2

2 2 1

입력 형식

첫째 줄에 K와 N이 공백을 사이에 두고 주어집니다.

1≤K≤4

1≤N≤8

출력 형식

조건을 만족하는 서로 다른 순서쌍의 개수 만큼의 줄에 걸쳐 한 줄에 하나씩 순서쌍의 상태를 공백을 사이에 두고 출력합니다. 이때 앞에서 부터 봤을 때 사전순으로 앞선 순서쌍부터 출력합니다.

풀이

백트레킹으로 수의 조합을 구하는데 조건메 맞게(여기서는 하나의 숫자가 연속 3번 이상 나오지 않도록) 조건 처리를 해주면된다. 3번 이상 연속되었는지 확인하기 위해 필요한 변수 num(앞에 온 숫자) 와 count(연속 개수)를 재귀함수의 파라미터로 설정하여 문제를 풀었다.

JAVA 코드

import java.io.*;
import java.util.*;

public class Main {

    static int K, N, arr[];
    static StringBuilder sb = new StringBuilder(); 

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st = new StringTokenizer(br.readLine()); 

        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken()); 

        arr = new int[N]; 
        solve(0, 0, 0);

        System.out.println(sb); 
    }

    static void solve(int cnt, int num, int count){
        if(cnt >= N){
            for(int i=0; i<N; i++){
                sb.append(arr[i]).append(" "); 
            }
            sb.append("\n"); 
            return; 
        }

        for(int i=1; i<=K; i++){
            if(num == i){
                if((count+1) >= 3) continue; 
                arr[cnt] = i; 
                solve(cnt+1, num, count+1);
            }else{
                arr[cnt] = i; 
                solve(cnt+1, i, 1); 
            }
        }
    }


}