문제https://www.acmicpc.net/problem/17609시간 제한메모리 제한solved.ac 티어1초(추가 시간 없음)512MB골드 5풀이 밀린 문제이다. 일반적인 회문은 원래 문자와 뒤집은 문자가 같은 것을 의미하지만, 해당 문제에서는 유사 회문이라는 개념을 제시한다. 유사회문이란 원래 회문은 아니지만 문자를 단 한개를 지웠을 때 회문이 되는 문자를 의미한다. 이 문제에서는 어떤 문자가 회문인지, 유사회문인지, 그것도 아닌지 모두 판단해보는 문제이다. 일반적인 회문 판단은 풀이할 필요가 없을 듯하니, 코드를 바로 읽어보면 될 것 같다. 우리가 중요하게 봐야하는건 유사회문 판별이다. 일반적인 회문처럼 문자열의 맨 앞과 맨 뒤를 검사하되, 중간에서 다른 문자를 만날수도 있을 것이다. 하지만..
문제https://www.acmicpc.net/problem/12904시간 제한메모리 제한solved.ac 티어2초512MB골드 5풀이 밀린문제 풀이다. 이전번에 풀이한 12919번(https://codejin.tistory.com/282) 보다 덜 복잡한 문제이다. 저번 문제는 b를 추가한 후 문자열을 뒤집었기 때문에 문자열의 맨 앞과 맨 뒤를 고려해야하는 문제였지만. 이번 문제는 이보단 덜 복잡하다. 이 문제 역시 S->T로 가는 것은 경우의 수가 매우 많다. 문자열을 뒤집는 연산이 끼어있기 때문에, S에 적당히 연산을 한 S'가 T의 부분문자열이 아닐수도 있다. 부분문자열이더라도 여러 곳에서 등장할 수 있으며, 이때마다 어떤 연산을 고르는 것이 최적일지는 구분하기 힘들다. 하지만 T->S로 바꿔보..
문제https://www.acmicpc.net/problem/12919시간 제한메모리 제한solved.ac 티어2초512MB골드 5풀이 밀린 문제 정리다. 이 문제도 역발상이 중요한 문제이다. S->T로 가는 것이 어렵다면, 그 역방향으로도 갈 수 있는지 생각하는 유연함이 필요하다. 저번 16953번(https://codejin.tistory.com/268)에서도 반대 방향으로 역추적하는 방식을 사용하는 풀이를 보이기도 했었다. 이런 발상을 바로 할 수 있도록 연습을 더 해야겠다. 이 문제는 어떻게 역추적을 하는지 생각해보자. 문제에서 말하는 연산을 위에서부터 각각 a, b연산이라고 간단하게 부르기로 하자. S->T로 가기 위해서는 a작업을 할수도 있고, b작업을 할 수도 있다. 당연히 모든 경우의 수..
