글 읽기 - 메모이제이션 이렇게 하는거 아닌가요..?

s2lsh90 6년 전 0

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

#include <stdio.h>
int N;
int M;
int chk[2002][2002];
int arr[2001];
int DFS(int S, int E) {
	if ((S < 0) || (E < 0)) return 0;
	if (E < S) return 0;
	if (E == S) {
		chk[S][E] = 1;
		return 1;
	}
	if (chk[S][E]) return 1;
	if (arr[S - 1] == arr[E - 1]) {
		if (DFS(S + 1, E - 1)) {
			chk[S][E] = 1;
			return 1;
		}
		else {
			return 0;
		}
	}
	else {
		return 0;
	}
}

int main(void) {
	int S, E;
	scanf("%d", &N);
	int sol;
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &S, &E);
		sol = DFS(S, E);
		printf("%d\n", sol);
	}
}

ainch96 6년 전 1

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

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

아닌가요?

s2lsh90 6년 전 0

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

jjwdi0 6년 전 1

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

s2lsh90 6년 전 0

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

jjwdi0 6년 전 1

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

1 2 3 4 5 같은 경우에는

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

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

다시 탐색하게 되겠죠?

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

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

ainch96 6년 전 1

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

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

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

#include <stdio.h>
int N;
int M;
int chk[2002][2002];
int arr[2001];
int DFS(int S, int E) {
	if (E < S) 
		return 1;
	if (chk[S][E] != -1)
		return chk[S][E];
	if (S==E)
		return chk[S][E] = 1;
	if (arr[S] != arr[E])
		return chk[S][E] = 0;
	else
		return chk[S][E] = DFS(S + 1, E - 1);
}

int main(void) {
	int S, E;
	scanf("%d", &N);
	int sol;
	for (int i = 1; i <= N; i++) {
		scanf("%d", arr+i);
	}
	for (int i = 0; i < 2002; ++i){
		for (int j = 0; j < 2002; ++j){
			chk[i][j] = -1;
		}
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &S, &E);
		sol = DFS(S, E);
		printf("%d\n", sol);
	}
}

s2lsh90 6년 전 1

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

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

문제

문제

출처

ICPC

메모이제이션 이렇게 하는거 아닌가요..?

s2lsh90 6년 전 0

ainch96 6년 전 1

s2lsh90 6년 전 0

jjwdi0 6년 전 1

s2lsh90 6년 전 0

jjwdi0 6년 전 1

ainch96 6년 전 1

s2lsh90 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말