글 읽기 - 9465 스티커 문제 질문드립니다.

blue5323 8년 전 0

문제를 우선 왼쪽부터 시작해서 첫 자신의 좌표가 (a,b)였을 때 a가 1행인지 2행인지에 따라서

두 가지 방법으로 재귀함수가 진행되도록 하였습니다.

● . . . . .

. ○○ . . .

혹은

. ○○ . . .

● . . . . .

의 상황과 같이 ●을 선택한다면 다음 두 가지의 ○들 중 한가지를 선택하여 진행하도록 소스를 짜보았습니다.

cache 배열도 선언하여 메모이제이션도 만들어 보았습니다.

제가 생각한 알고리즘 자체가 틀린것인지, 구현 과정 중에서 잘못된 것인지 궁금합니다.

PS. 이 스티커문제의 다른 질문에 대한 답변도 읽어보았으나 cache를 cache[3][100001]과 같이 설정한 부분에서 위를 골랐을 때, 아래를 골랐을 때, 안 골랐을 때로 구분 하셨던데.. 안 골랐을 때는 전개가 어떤식으로 이루어지는지에 대해 이해를 못하여 또 다른 질문을 올리게 되었습니다.

답변 주시면 갑사하겠습니다.

#include <stdio.h>
int n;
int A[2][100001],cache[2][100001];

int max(int a,int b){
	if(a>b) return a;
	return b;
}

int solve(int a, int b){

	if(b>n) return 0;

	int& ret=cache[a][b];
	if(ret!=-1) return ret;

	if(a==0) ret=max(solve(1,b+1),solve(1,b+2))+A[a][b];
	
	else  ret=max(solve(0,b+1),solve(0,b+2))+A[a][b];
	
	return ret;
}

int main(){

	int T;
	scanf("%d",&T);

	while(T--){
		scanf("%d",&n);

		for(int i=0;i<2;i++)
			for(int j=0; j<n;j++)
				scanf("%d",&A[i][j]);
		
		for(int i=0;i<2;i++)
			for(int j=0; j<n;j++)
				cache[i][j]=-1;
		
		printf("%d\n",max(solve(1,0),solve(0,0)));

	}

}

yukariko 8년 전 0

스티커의 범위가 [0,n) 이기 때문에 종료조건은 b > n 이 아닌 b >= n이 되어야 합니다.

굳이 고르지 않았을때의 3가지로 나눌 필요는 없습니다.

나눈 이유는 아마 max(solve(1,0),solve(0,0)) 로 호출하지 않고 함수 한번의 호출로 답을 찾고싶어서 그렇게 한것으로 보입니다.

blue5323 8년 전 0

정말 감사드립니다. 해결이 되었네요.

사소한 부분에서 실수가 있었네요ㅜㅜ..

실례가 안된다면 한가지 더 궁금한 점을 여쭙고 싶습니다.

원래 코드였던 b > n으로도 예제의 입력에서는 적절히 나왔으나 제출했을 때 오답을 받았던거 어떤 차이가 있던 것인지 궁금합니다.

yukariko 8년 전 1

답변이 늦어서 죄송합니다.

b > n 으로 틀리는 이유는 초기화와 관련이 있습니다.

예를들어 이전 테스트 케이스는 N이 10 이었고,

지금의 테스트 케이스는 N이 9라고 합시다.

지금의 코드는 cache[0][8] 까지를 -1로 초기화 합니다.

즉, cache[0][9]나, cache[1][9]는 -1로 초기화 되지 않은 상태로 이전 테스트케이스에서의 결과가 남아있는것이죠.

그 상태로 solve함수에서 b가 N인 9라고 가정해보죠.

b > n 일때만 0을 리턴하기 때문에 b == n 인 경우는 통과하게되고,

cache[a][b] 에서 -1이 아닌 이전 테스트케이스의 결과가 남기 때문에 이 코드가 틀리게 되는 것입니다.

범위를 잘 고려하여 코드를 작성하는것이 중요하겠죠?

하지만 매번 배열의 범위나 이전 테스트케이스와의 관계를 고려해주는것은 쉬운 작업이 아니기때문에,

그러한 사태를 미연에 방지하는 코드를 작성하는것이 바람직할 수 있습니다.

예를들면 cache배열의 초기화를 memset(cache, -1, sizeof(cache)) 함수를 통해 일괄적으로 초기화 하는것이죠.

blue5323 8년 전 0

댓글을 바로 이해가 되었습니다.

정말 감사합니다. 좋은 정보 받아갑니다!!

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

문제

문제

출처

ICPC

9465 스티커 문제 질문드립니다.

blue5323 8년 전 0

yukariko 8년 전 0

blue5323 8년 전 0

yukariko 8년 전 1

blue5323 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말