글 읽기 - 두 코드의 차이를 잘 모르겠습니다.

juhongkim2 6년 전 0

첫번째 풀이는

해당 마을을 방문할 수 있는 경우의 수를 구할 때 매번 %1000000000연산으로 저장했습니다.

왜냐하면 문제에서 9자리수를 넘어가면(>=1000000000) 뒤에 9자리만 출력하라고 했기때문에...

제 생각엔 매번 %1000000000 해주면 어차피 9자리를 넘어갈 일이 없기때문이라고 판단했기 때문입니다.

그런데 이렇게 풀면 자꾸 45퍼에서 에러가나서

두번째 풀이는

구조체를 따로 만들어서 합연산의 결과가 1000000000을 넘어가면 overflow를 1로 만들어주고

합에서 1000000000을 빼주도록 하였습니다.

제 생각에는 결과를 1000000000로 나눈 나머지를 저장해주는거나

1000000000를 넘어갔을때 overflow를 1로 만들고 합에서 1000000000를 빼는거나 별반 차이가 없어 보이는데

왜 결과에서 차이가 날까요?

/*이렇게 하면 틀림*/
ll Solve(int cur)
{
	int i,next;

	if(flag==1)
		return -1;

	if(check[cur]==2)
		return cnt[cur];
	if(check[cur]==1){
		flag=1;
		return 0;
	}

	check[cur]=1;
	if(cur==2)
		cnt[cur]=1;
	for(i=0;i<g[cur].size();i++){
		next=g[cur][i];
		if(connected[next]==1 && reconnected[next]==1)
			cnt[cur]=(cnt[cur]+Solve(next))%1000000000;//1000000000를 넘어가지 않도록 %연산을 사용
	}
	check[cur]=2;

	return cnt[cur];
}

sgchoi5 6년 전 0

COCI 문제는 대회에서 사용했던 TC(Judge Data) 가 공개되어 있으니...

http://gooddaytocode.blogspot....

한 번 돌려보시길...

lilykju 5년 전 1

test data를 보니까 나눠서 9자리 미만이면 앞에 0을 붙여줘야 되네요..

mic1021 5년 전 2

저도 이것때문에 고민했는데 답을 알려드리자면

만약 %를 사용해서 답을 구한 경우 4라는 결과값이 나왔다면 이 값이 1000000004인지 4인지 구별할수가 없게됩니다.

구별 못하는게 왜 문제가 되느냐하면...

문제 출력조건에서 9자리를 넘어가는 경우에는 뒤 9자리만을 출력하라고 했으므로 만일 최종 답이 1000000004라면 000000004라 출력되야 정답이고 4라면 4가 출력되면 정답이 되는것이지요 ..

그래서 정답 소스에서는 overflow용으로 flag를 만들어서 경우에 따라서 출력한것이고요

akswnd98 3년 전 0

와 진짜 극악무도하네요.

정답률 19%의 비밀이 자릿수에...

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

문제

문제

출처

ICPC

두 코드의 차이를 잘 모르겠습니다.

juhongkim2 6년 전 0

sgchoi5 6년 전 0

lilykju 5년 전 1

mic1021 5년 전 2

akswnd98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말