글 읽기 - 39%에서 WA 뜨는데 어떤 케이스에서 틀리는걸까요?

jaimemin 5년 전 0

그리디하게 제일 큰 수부터 빼가면 최소로 이긴다고 판단하고 코드를 작성했습니다.

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

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long x, y;
	cin >> x >> y;

	if (!x && !y)
		cout << 0 << "\n";
	else
	{
		long long k = 1;
		bool possible = true;
		long long pSum = 0;
		//1 ~ K의 합
		while (1)
		{
			pSum += 2 * k - 1;
			//가능한 경우
			if (x + y == pSum)
				break;
			//가능하지 않은 경우
			if (x + y < pSum)
			{
				possible = false;
				break;
			}
			k++;
		}

		if (!possible)
			cout << -1 << "\n";
		else
		{
			long long result = 0;
			//제일 큰 수부터 뺀다
			for (long long i = k; i >= 1; i--)
			{
				if (x == 0)
					break;
				if (2 * i - 1 <= x)
				{
					x -= 2 * i - 1;
					result++;
				}
			}
			cout << result << "\n";
		}
	}
	return 0;
}

seico75 5년 전 2

11 14

jaimemin 5년 전 0

감사합니다!

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

문제

문제

출처

ICPC

39%에서 WA 뜨는데 어떤 케이스에서 틀리는걸까요?

jaimemin 5년 전 0

seico75 5년 전 2

jaimemin 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말