[백준 알고리즘 - 1579] 암호만들기 -java(재귀)

우선 문제는 

최대 3C15 의 경우의 수이기 때문에 모든 경우의 수를 탐색해보아도 제한 시간 안에 해결할 수 있다.

재귀호출을 이용할 때는

- 조건을 만족하지 못하고 종료하는 조건

- 조건을 만족하고 카운트 또는 출력하는 조건

- 다음 경우의 수 ( 재귀호출 )

이 세가지를 고려해야 한다.

순서대로 

만족하지 못하고 종료하는 조건은, 

1. 주어진 배열 끝까지 탐색하였는데 pw의 길이를 충족하지 않는 경우

2. pw의 길이를 충족하였으나 모음, 자음 조건을 만족하지 않는경우

조건을 만족하고 출력하는 조건은,

1. 패스워드 길이를 만족하고 모음, 자음 조건을 만족하는 경우

다음 경우의 수는,

1. 현재 탐색하는 배열[인덱스]를 포함하는 경우

2. 혐재 탐색하는 배열[인덱스]를 포함하지 않는 경우

로 짤 수 있다.

코드는 다음과 같다.

아 호출 전에 입력받은 배열은 미리 정렬시켜서 순서는 고려하지 않아도 되도록 구현하였다.

import java.util.Arrays;
import java.util.Scanner;


class Main{

    //z: 자음의 수, m:모음의 수, arr 주어진 문자 배열, idx 현재 검사하는 idx, pw 현재까지 결정한 패스워드, L 선택해야하는 수
	public static void password(int z, int m, char[] arr, int idx, String pw,int L) {
		if(idx >=arr.length  && pw.length() !=L )//만족하지 못할 때
			return;
		if( pw.length() == L && (m < 1 || z < 2 )) // 만족하지 못할 때 2
			return;
		if(pw.length()==L && m >=1 && z>=2) { //조건을 만족하는 경우 
			System.out.println(pw);
			return;
		}
		
		if(arr[idx]=='a' || arr[idx]=='e' || arr[idx]=='i' || arr[idx]=='o'|| arr[idx]=='u')
			password(z,m+1, arr, idx+1, pw+arr[idx], L );//모음인 경우
		else
			password(z +1 ,m, arr, idx+1, pw+arr[idx], L );//자음인 경우
		
		password(z,m, arr, idx+1, pw, L );//선택하지 않고 다음 인덱스로 넘어감 
	}
       public static void main(String[] args){
    	   Scanner scan=new Scanner(System.in);
    	   int L=scan.nextInt();
    	   int C=scan.nextInt();
    	   
    	   char arr[]= new char[C];
    	   for(int i=0; i<C; i++)
    		   arr[i]=scan.next().toCharArray()[0];
    	   
    	   Arrays.sort(arr);
    	
    	   password(0,0, arr, 0,"" , L );
    	   
    	   
       }
       
  }

재귀호출을 완벽하게 이해하고 점화식을 구할 수 있어야 DP도 수월하게 학습할 수 있지 않을까싶다 화이팅!