s2lsh90   2년 전

메모제이션 했다고 생각하는데도 시간초과 나오네요 ..

ainch96   2년 전

근데 DFS 내에서 5번째 if문 안에 들어가는 값은

arr[S+1]==arr[E-1] 

아닌가요?

s2lsh90   2년 전

S , E 는 1부터시작하는데 배열은 0부터 시작해서 그거 줄여줬던 부분이에요~ 양쪽 마지막 숫자 같고 나머지는 DP확인해서 없으면 계속 재귀 돌리는부분이구요 ㅠㅠ

jjwdi0   2년 전

배열에 팰린드롬이 하나도 없는 경우를 생각해보세요.

s2lsh90   2년 전

그럴수가 있나요 ?? S 하고 E가 같으면 무조건 팰런드롬 아닌가요??? 

jjwdi0   2년 전

아 제말은 길이 2 이상인 팰린드롬이 없을 때를 말한 겁니다.

1 2 3 4 5 같은 경우에는

chk[i][j]가 i == j인 경우를 제외하고 0이 저장되어 있으니까

구간 [i, j]에 대해 질문이 들어오면

다시 탐색하게 되겠죠?


그래서 우선 [i, j]가 팰린드롬이 아니더라도

chk[i][j]를 0이 아닌 값으로 바꾸어야 다음에 같은 질의에 대해 미리 저장된 값을 쓸 수가 있습니다.

ainch96   2년 전

그래서 저는 jjwdi0 님의 말씀에 맞게 코드를 아래와 같이 구현했습니다. 

chk[i][j] 초기값을 -1으로 설정하고, 

만약 부분 배열이 팰린드롬이라면 1, 아니라면 0을 저장하는 방식으로 메모이제이션을 실행했습니다.

s2lsh90   2년 전

햐.. ㅋㅋㅋ 하나만 생각하고 둘은 생각 못했네요 두분다 너무 감사드립니다. 메모제이션이 어떤거인지 조금이나마 알것 같습니다 !!

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