글 읽기 - 디지털 카운터 질문입니다.

jaykay 7년 전 0

분류는 dp 라고 되어있지만, 제가 생각할 수 있는 input 으로는 그냥 naive 하게 풀어도 모두 시간 내에 풀 수 있을거라 생각했는데 답을 제출하니 시간 초과라고 나오네요.

제가 문제를 잘 이해하지 못 했거나, 제가 생각하지 못 한 예제가 있는 것 같은데 어떤 부분이 틀렸는지 알려주시면 감사하겠습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>

#include <string>
using namespace std;
typedef long long ll;

const int segments[10] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 5 };

int n, targetSegmentNum;
ll startNum, lastNum;

int getSegmentNum(ll number)
{
	int ret = 0;
	int remaining = n;
	while (number > 0)
	{
		remaining--;
		ret += segments[number % 10];
		number /= 10;
	}
	ret += (segments[0] * remaining);

	return ret;
}

int bruteForce(ll number)
{
	int changedSegmentNum = -1;
	int ret = 0;
	while (changedSegmentNum != targetSegmentNum)
	{
		ret++;
		if (number == lastNum)
			number = 0;
		else
			number++;
		changedSegmentNum = getSegmentNum(number);
	}
	return ret;
}

int main()
{
	string strStartNum;
	cin >> strStartNum;

	n = strStartNum.size();
	startNum = stoll(strStartNum);
	lastNum = pow(10, n) - 1;
	
	for (int i = 0; i < n; i++)
		targetSegmentNum += segments[strStartNum[i] - '0'];
	
	cout << bruteForce(startNum) << endl;

	return 0;
}

leejk9592 7년 전 0

111111111111111

답이 1000000000000000 일겁니다

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

문제

문제

출처

ICPC

디지털 카운터 질문입니다.

jaykay 7년 전 0

leejk9592 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말