글 읽기 - 10844번 틀렸습니다 뜨는데 왜인지 잘 모르겠습니당!

dokrsky 8년 전 0

제가 손으로 3까지 써봤는데여

1 = 9

2 = 17

3 = 32

4 = 61 이 나오더라구요

그래서 제가 생각한 게

f1 = (((f1 * 2) % MOD) - (m%MOD))%MOD;

m++;

이 방식인데요

어떤 자릿수건 마지막이 0과 9라면 만들 수 있는 수는 1가지, 1가지 잖아요?( 2는 1 또는 3으로 2가지 )

1..2..3...4....... 100 까지 계속 자릿수가 늘때마다 0과 9는 반복되어서 나타나기 때문에 위의 식이 맞다고 생각하는데

어디가 잘못된 접근일까요? ㅠㅠ

#include <iostream>
using namespace std;
int main()
{
	long MOD = 1000000000;
	int f1 = 9;
	int num = 0;
	int m = 1;
	scanf("%d", &num);

	for (int i = 1; i < num; i++)
	{ 
		f1 = (((f1 * 2) % MOD) - (m%MOD))%MOD;
		m++;
	}
	cout << f1 << endl;
	return 0;
}

ntopia 8년 전 1

%MOD 한 것 끼리 빼고 다시 %MOD할 때는 주의하셔야 합니다

(-3) % 100 의 계산결과가 97이 아니라 -3 이기 때문입니다...

dokrsky 8년 전 0

cubelover 님

ntopia님 감사합니다!

그런데

ntopia 님, 저 문제에선 -3이 나오지 않으니 고려하지 않아도 되는사항이죠?? 라고 여쭤볼려고 했는데

나중에 f1 * 2 % MOD 부분이 매우 작은 수로 나오게 되고, m % MOD가 이 보다 큰 수라면 -3이 나올 수 있겠네요.. 감사합니당!!

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

문제

문제

출처

ICPC

10844번 틀렸습니다 뜨는데 왜인지 잘 모르겠습니당!

dokrsky 8년 전 0

ntopia 8년 전 1

dokrsky 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말