글 읽기 - 왜 틀렸는지 알고 싶습니다. 반례가 있을까요?

yhun6191 1년 전 0

입력 범위가 1~80인데 1부터 15 정도까지 다 답이 출력되고, 게시판에 있는 25, 52, 59 같은 숫자를 넣어서 비교해봐도 전부 정답이 출력됩니다.

어디서 틀렸는지 정말 모르겟네요 ㅠㅠ 혹시 반례나 틀린이유를 알 수 없을까요?? 너무 답답합니다 ㅠㅠ

#include<iostream>
#include<algorithm>
using namespace std;
int N;
int Sequence[80];

int choose_next(int curr, int value) //curr : 0~79번 중 현위치, value : 현위치에 들어갈 수
{
	Sequence[curr] = value;
	if (curr == N - 1) {
		for (int i = 0; i < N; i++) { cout << Sequence[i]; }
		exit(0); // 최초 완성시 출력후 종료
	}
	for (int next_value = 1; next_value <= 3; next_value++)
	{
		if (next_value == value) { continue; } // 연속한 두 숫자는 패스
		bool can_put = true;
		for (int i = 1; i < (curr + 2) / 2; i++) // 같은 부분수열 유무 판별
		{
			int sum_A = 0;
			int sum_B = 0; 
			int A = curr + 1;
			int B = curr - i;
			Sequence[A] = next_value;

			int d = 1;
			for (int j = 0; j <= i; j++)
			{
				sum_A += d*Sequence[A - j];
				sum_B += d*Sequence[B - j];
				d *= 10;
			}
			if (sum_A == sum_B) { can_put = false; break; } // 같은 부분수열 발견
		}
		if (can_put) { choose_next(curr + 1, next_value); }
	}
}

int main()
{
	cin >> N;
	choose_next(0, 1);
}

eaken 1년 전 0

sum_A, sum_B, d에서 오버플로우가 발생합니다.

long long으로 고쳐도 턱없이 부족할 거예요.

수열 길이는 최대 80이고 부분 수열은 최대 40까지도 올라가는데

d를 10으로 두면 길이가 부분 수열 길이가 40일 경우 d가 10^40이 돼버려요.

long long은 대략 9*10^18까지 표현 가능하고요.

d로 둘 수 있는 가장 작은 정수 값은 3보다 큰 4인데 d를 4로 둔다고 하더라고 4^40이 long long 범위를 초과합니다.

그래서 부분 수열을 정수로 변환 후 비교하시면 안 됩니다.

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

문제

문제

출처

ICPC

왜 틀렸는지 알고 싶습니다. 반례가 있을까요?

yhun6191 1년 전 0

eaken 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말