티스토리 뷰

반응형

Bark to Unlock

난이도 3/10 

까다롭다면 까다로울 수 있는 문자열 문제.


문제보기

http://codeforces.com/problemset/problem/868/A



캡쳐하다가 뭔가 꼬여서 다날라가버렷다 ㅡ.ㅡ;; 대충씀

Input 

패스워드가 주워진다. (소문자 두글자) 
Kashtank가 짖을 수 있는 횟수가 주어진다. (1<=n<=100)
n line에 걸쳐 kashtanka의 짖은 두 글자가 주어진다.

Output

패스워드를 풀 수 있는면 YES , 또는 NO로 출력하라. 



예제 1에서는 주어진 문자 "ah", "oy", "to", "ha" 를 조합해서 "ya"를 만들수있다. "oyah .."

예제 2에서는 만들수 없다.

예제 3에서는 "hahaha ..." 로 "ah"를 생성할 수 있다.


문제해설 

문자열 관련 알고리즘은 대개 중급~고급이다.(난 풀지못한다) 근데 contest 의 첫문제로 나오니 당황. 뭔가 쉬운 방법이 있을거라 생각했다.

입력된 문자의 두번째가 패스워드의 첫번째와 맞다면 상태1로, 입력된 문자의 첫번째가 패스워드 두번째와 같다면 상태2로, 입력된 문자열 전체가 패스워드 전체와 같다면 상태 3으로.

상태1에서, 또 다시 입력된 문자의 첫번째가 패스워드 두번째와 같다면 상태3으로

상태2에서, 또 다시 입력된 문자의 두번째가 패스워드 첫번째와 같다면 상태3으로.

라는 약간 FSM 닮음의 형태로 다뤄보았다. 그러니까 풀렸다. 다행이었다.


소스보기

https://github.com/ingyeoking13/algorithm/blob/master/cf/implementation/p868a.c


반응형

'알고리즘 문제 > implementation' 카테고리의 다른 글

879B: Table Tennis  (0) 2017.10.27
879A : Borya's Diagnosis  (0) 2017.10.27
codeground : 다트게임  (0) 2017.10.08
868B : Race Against Time  (0) 2017.10.08
Codeforces: Between The Offices  (0) 2017.10.02