[codeground] 9. 화학자의 문장

codeground - Practice - 연습문제 - 9. 화학자의 문장
문제 : https://www.codeground.org/practice/practiceProblemList

---

vector<vector<bool>> alph(26, vector<bool> (27, false));
vector<int> check;//-1: 방문 x. 0: 불가능. 1: 가능

화학원소 기호들로 위 배열 2개를 채웁니다.
alph 배열은 원소 기호들로 문자를 만들 수 있는지 여부를 저장합니다.
예를 들어 alph[0('a')][0] 은 a를 만들 수 있는지를 뜻하고 alph[0('a')][1('a')]은 aa를 만들 수 있는지를 뜻합니다.
check 배열은 입력받은 문자열을 s라고 했을 때 check[ind] 는 s[ind~끝]에 해당하는 부분 문자열을 화학 원소 기호들로 만들 수 있는지를 뜻합니다. 예를 들어 s = "abcde" 에서 s[2]는 "cde"를 화학 원소 기호들로 만들 수 있는지를 의미합니다. 아직 확인해보지 않았다면 -1, 확인해봤을 때 가능하다면 1, 불가능하다면 0이 들어갑니다.

함수 bool go(ind)는 s[ind~끝]을 만들 수 있는지를 반환합니다.
1. alph 배열을 이용해서 한글자로 s[ind]를 만들 수 있다면(alph[s[ind]-'a'][0] == true) 이후의 문자열(s[ind+1~끝])을 만들 수 있냐 없냐에 따라 s[ind~끝]을 만들 수 있는지가 정해지므로 check[ind] = go(ind+1)이 됩니다.
2. alph 배열을 이용해서 두글자로 "s[ind]s[ind+1]"를 만들 수 있다면 (alph[s[ind]-'a'][s[ind+1] - 'a' + 1] == true) 이후의 문자열 (s[ind+2 ~ 끝])을 만들 수 있느냐에 따라 check[ind]가 정해지므로 check[ind] = go(ind+2)가 됩니다.

1, 2 번을 실행했을 때 한 번이라도 check[ind]가 true가 될 수 있다면 check[ind]는 1이 갱신되고 두 결과 모두 false가 된다면 0으로 갱신합니다. 그리고 그 결과를 반환합니다.

---

소스 코드 : https://github.com/fpdjsns/Algorithm/blob/master/codeground/9.%20%ED%99%94%ED%95%99%EC%9E%90%EC%9D%98%20%EB%AC%B8%EC%9E%A5.cpp

---

bottom-up 방법으로 코드를 작성했고 go(ind)에서 ind가 같은 경우가 여러번 호출되어 이미 구한 경우를 다시 구하는 시간 낭비를 방지하기 위해서 check 배열을 만들었습니다. (memoization)
메모이제이션 안했다가 8점인가 까였었네요;;