글 읽기 - 반례를 찾습니다.

adfsfsf 5년 전 0

기본 아이디어는 2개입니다. 하나는 https://www.acmicpc.net/board/...에 적은 것이고, 다른 하나는 s와 k가 주어졌을 때의 최대 곱은 https://www.acmicpc.net/board/...에서 생각한 아이디어로 나온 값과 s-i와 k-i를 다시 s와 k로 놨을 때의 결과값과 비교했을 때 더 큰 값이 최댓값이라는 점입니다. 단, i는 현재 k값보다 작습니다. 이 2가지를 합치면 s/k가 1인 경우도 해결됩니다. 그럼에도 오답 처리가 되는데, 이외의 반례를 알고 싶습니다. 아래는 2가지를 합친 결과입니다.

#include <iostream>
#include <cmath>
using namespace std;
long long int getting(long long int s, long long int k);
int main(void)
{
	long long int s, k;
	cin >> s >> k;
	cout << getting(s, k) << endl;
	return 0;
}
long long int getting(long long int s, long long int k)
{
	long long int max = 0, i, t, a, b, p;
	if (k == 1)
		return s;
	a = s / k;
	b = s % k;
	if (a != 1)//기본적인 아이디어로 편차가 가장 작을 때 최댓값이 나온다는 가설을 따른다. a == 1일 때는 잘못된 결과가 나온다.
	{
		max = pow(a, (k - 1)) * (a + b);
		p = (a - 1) * (k - 1);
		p = pow((a - 1), (k - 1)) * (s - p);
		max = max > p ? max : p;
		p = (a + 1) * (k - 1);
		if (s > p)
		{
			p = pow((a + 1), (k - 1)) * (s - p);
			max = max > p ? max : p;
		}
	}
	for (i = 1; i < k; i++)//k보다 작은 i값에 대하여 s-i, k-i를 각각 s, k로 갖는 최댓값과 비교해서 더 큰 값이 최댓값이다.
	{
		t = getting(s - i, k - i);
		max = max > t ? max : t;
	}
	return max;
}

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

문제

문제

출처

ICPC

반례를 찾습니다.

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말