글 읽기 - 아무리 생각해도 반례를 못 찾겠어요 ㅠ ㅠ

yoonfy4280 5년 전 0

예제는 다 맞게 나오는데, 다른 반례가 뭐가 있는지 모르겠어요 ㅠ ㅠ.

풀이 원리를 => 문자열개수 + (K-1)*(문자열개수-겹쳐지기사작하는 부분부터의 문자열개수)

이렇게 생각했는데,

무슨 문제인지 잘모르겠어요ㅠ ㅠ

처음과 마지막이 다를 때
처음과 마지막이 같을 때

=> 처음과 겹치는 부분이 중간 부터일 경우

3. 문자 하나만 쓰일 때

이런 경우 보다 더 있나요?

#include<iostream>
#include<cstring>
using namespace std;

int main() {
	char Arr[500001];
	int K, len, j = 0, temp, flag = 0;
	long long int A;

	cin >> Arr;
	cin >> K;
	len = strlen(Arr);

	for (int i = 1; i < len; i++) {
		temp = i;

		while (temp < len && Arr[j] == Arr[temp]) {
			
			temp++;
			j++;
			if (temp == len) {
				flag = 1;
			}

		}

		if (flag == 1) {
			break;
		}
		else {
			j = 0;
		}

	}
	A = ((len - j) * (K - 1)) + len;

	cout << A;

	return 0;
}

njw1204 5년 전 0

A = ((len - j) * (K - 1)) + len;

이 부분에서 int끼리 곱셈이 이루어져 오버플로우가 일어납니다.

예를 들어 입력으로 aaaa....(9999개)..b 300000 을 넣어보면 음수값이 출력됩니다.

변수들을 모두 long long으로 고치면 이 부분은 해결될 것 같습니다.

근데 이걸 고치고 제출하시면... 이번에는 시간초과가 뜰 것 같네요.

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

문제

문제

출처

ICPC

아무리 생각해도 반례를 못 찾겠어요 ㅠ ㅠ

yoonfy4280 5년 전 0

njw1204 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말