(JAVA) 백준 2661번 : 좋은수열

 

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

2661번: 좋은수열

 

 

이는 백트래킹 문제이다.

 

처음에 짠 알고리즘이 정답과 얼추 비슷했지만 틀렸고,

 

메모리 초과까지 발생하는 바람에

 

 

백트래킹 방식으로 시도해봤다.

 

 

 

정답과 정답을 도출하는 해설 방법만 기억하면 된다.

 

 

 

매커니즘

---

 이 문제는 세 가지를 중요시하면 된다.

 

 

1) N인 수열이 존재할 때, 수열은 전부 1, 2, 3 세 개의 숫자 중 하나로 이루어져 있다.

 

2) 그 중, 반복된 문자열(여기선 숫자들) 이 붙어있지 않은 수열이 좋은 수열이고, 이를 구하는 문제이다.

 

3) 그 좋은 수열들 중, 가장 작은 수를 출력하면 된다.

 

 

위 세 가지를 생각하며 알고리즘을 짜면 된다!

 

 

 

 1. 1) 을 구하기 위해 한 자리마다 1 ~ 3까지 임시로 끝에 넣고, 탐색하며 추가 가능한 숫자를 집어넣는다.

 

 2. 가능한 숫자를 파악하기 위해 1개부터 이전까지 구한 수열의 길이 + 현재 임의로 집어넣은 1~3 중 하나의 길이의 절반까지 for문으로 탐색하며 같은 문자열인지 체크.

 

 3. 같은 문자열이 나오는 순간 임시로 넣은 숫자는 사용 불가능. -> 다음 숫자를 넣고 재진행

 

 4. 같은 문자열이 하나도 발견되지 않음 = 좋은 수열. 임시로 넣은 숫자를 확정시키고 다음 숫자를 넣기 위해 백트래킹진행.

 ** 백트래킹 진행은 함수 재귀 호출과 같다.

 

 5. 가장 먼저 N자리의 수열을 구한 경우, 가장 작은 수가 되므로 굳이 다음 수열을 구할 필요가 없음. 그렇기 때문에 재귀 호출되는 다음 함수들은 탐색할 필요 없이 종료시키면 됨.

 *** 이를 위해 static boolean 변수를 생성하고 진행시키면 된다.

 

 

 

 

자세한 사항은 소스코드에 있습니다!

 

백트래킹.. 어렵다..

 

 

감사합니다!

 

 

 

소스 코드