dreammusic23   1년 전

제가 푼 방법은 다음과 같습니다.


1. input[i]에서 input[j]까지가 팰린드롬인지 확인합니다. (아래는 예제입력에 대한 팰린드롬을 체크한 내용입니다.)

스크린샷 2016-12-31 오전 12.44.58.png

2. 1.에서 확인할 때 i에서 시작해서 어떤 j로 끝나는 모든 팰린드롬의 길이중 가장 긴 것을 check[i]에 저장합니다. (아래는 그 값들 입니다.)

스크린샷 2016-12-31 오전 12.46.35.png

# 처음에는 Greedy하게 for loop으로 for( i = 0 ; i < len ; i += check[i], cnt++ ); 로 cnt를 세어줬으나 뒤쪽 2 5 3 1 1 1 2 1에서 5를 선택하지 않고 2를 먼저 선택하는것을 보고(AABDBADD에서 { A, ABDBA, DD }를 선택해야하는데 { AA, BDB, A, DD }를 선택해버림을 확인했습니다.


3. 그래서 문제를 이렇게 바꿨습니다.

      >> check배열에서 i번째 칸에서 1 ~ check[i] 칸만큼 전진할 수 있을 때, 마지막 칸을 밟을 때의 최소 횟수


4. 최종 결과입니다.

스크린샷 2016-12-31 오전 12.51.48.png

이렇게 풀었는데 틀렸다고 합니다...

도대체 어디서부터 잘못된 걸까요? 제가 맞은 부분이 있기는 한걸까요...? ㅠㅠㅠ


코드는 첨부했습니다.

댓글을 작성하려면 로그인해야 합니다.