백준 1759 - 암호 만들기

문제 출처: https://www.acmicpc.net/problem/1759

 

나의 접근 방법!

 

Backtracking 자체를 이해하기가 어려워서 하나하나 손코딩으로 입력해줘서 이해를 하였다.

 

풀이를 참고하여 이 문제를 이해하며 풀었는데 굉장히 어려웠다.

 

 

 

 

 

 

 

 

 

 

static void backTracking(int index, int cnt, int mo, int ja, String s) {

if(cnt == selectNum) {

if(mo>=1 && ja>=2)

System.out.println(s);

return;

}

 

if(index == maxNum) return;

 

if(strArr[index] == 'a' || strArr[index] == 'e' || strArr[index] == 'i' || strArr[index] == 'o' || strArr[index] == 'u')

backTracking(index+1, cnt+1, mo+1, ja, s+strArr[index]);

 

else backTracking(index+1, cnt+1, mo, ja+1, s+strArr[index]);

 

backTracking(index+1, cnt, mo, ja, s);

}

 

 

 

 

 

 

selectNum은 전체 숫자 갯수중에 몇개를 선택하여 조합할지 입력받은 값이고,

maxNum은 전체 입력 받은 숫자를 나타낸다.

 

위의 backTracking함수를 예를 들어 설명하면,

 

1. backTracking(0,0,0,0,"")에서 출발하여, 입력받은 숫자를 미리 한번에 정렬한 후, 

 

2. 첫번째 인덱스를 선택하여 자음인지 모음인지 판별한 후에 모음이면  mo+1을 해주고

 

3. 자음이면 ja+1을 해주며 백트레킹을 돌린다.

 

4. 함수의 종료 조건은 cnt가 출력할 알파벳 개수라면 출력해주고 return 해주고

 

5. index가 전체 숫자 갯수라면 리턴해준다. 인덱스는 n-1이기 떄문.

 

 

 

 

 

 

 

 

나의 전체 소스 코드: https://github.com/wopuv48/Algorithm_Practice_for_Tests/tree/master/algotest1