글 읽기 - 4초 정도 남기도 틀립니다. 반례가 무엇일까요?

epimiral 5년 전 0

코드는 아래와 같습니다.

설명도 아래 코드에 주석으로 달았습니다.

4초 정도 남기도 약 50프로 정도에서 실패했다고 뜹니다.

밑의 주석으로 달린 cout 부분의 주석을 제거하신다면 각각의 결과를 보실 수 있습니다.

답변 주시면 감사드리겠습니다!ㅎㅎ

// 2331.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int a, p; int a1; int check[236197] = {0,};  
int cal(int x)
{
	// x 를 넣으면 숫자를 계산해서 결과 출력
	int ans = 0;
	while (x != 0) {
		int num; int result = 0;
		num = x % 10; result = num;
		for (int i = 0; i < p - 1; i++) {
			result = result * num;
		}
		x = x / 10;
		ans += result;
		//cout << num << " " << result << " " << x << " "<< ans <<"\n";
	}
	return  ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> a >> p; // 입력
 // max는 구해지는 최대 수를 구합니다. 즉 모든 배열을 탐색안하기 위해서 사용함
	int max = 0; 
	max = a;
	a1 = cal(a);
	check[a]++;	check[a1]++;

	if (a1 > max) max = a1;
	//cout << a << " " << check[a] << "\n";
	//cout << a1 << " "<< check[a1] << "\n";

	// 숫자를 차례로 넣고 숫자가 나오면 check 배열의 숫자를 더합니다. check이 3인 배열이 나오면 멈춥니다. 
	if (a1 == a);
	else {
		do {
			int b;
			b = cal(a1);
			check[b]++;
			if (check[b] == 3) break;

			a1 = b;
			if (a1 > max) max = a1;
			//cout << a1 << " "<< check[a1] << "\n";
		} while (a1 != a);
	}

	//출력부 - check 배열이 1이면 cnt를 1씩 더합니다.
	int cnt = 0;
	for (int i = 1; i <= max; i++) {
		if (check[i] == 1) {
			//cout << i << " ";
			cnt++; 
		}
	}
	//cout << "\n";
	cout << cnt << "\n";

	// 4초에서 틀림
	system("pause");
    return 0;
}

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

문제

문제

출처

ICPC

4초 정도 남기도 틀립니다. 반례가 무엇일까요?

epimiral 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말