백준(BOJ) 14238번 출근 기록

문제 : https://www.acmicpc.net/problem/14238

14238번: 출근 기록

 

문제

스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다.

 

이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날엔 C만 출근했다는 뜻이다.

 

A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 올바른 것은 아니다. 예를 들어, B는 출근한 다음날 쉬어야 하기 때문에, "BB"는 절대로 나올 수 없는 출근 기록이다. 

 

출근 기록 S가 주어졌을 때, S의 모든 순열 중에서 올바른 출근 기록인 것 아무거나 출력하는 프로그램을 작성하시오.

 

풀이 :

A를 넣을때 a-1, b, c, A를 넣었으니 전코드는 'A'가 된다. 전전코드는 전코드가 된다.

 

이떄 A조건은 없다.

 

B를 넣을때 a, b-1, c, B를 넣었으니 전코드는 'B'가 된다. 전전코드는 전코드가 된다.

 

B를 넣을떄 조건은 전알파벳이 'B'여서는 안된다

 

C를 넣을때 a, b, c-1, B를 넣었으니 전코드는 'C'가 된다. 전전코드는 전코드가 된다.

 

C를 넣을때 조건은 전알파벳이 'C' 전전알파벳이 'C' 여서는 안된다. 

 

이렇게 재귀함수를 돌려주면서 다차원 캐쉬로 메모이제이션 해준다.

 

코드 ( C++ )