글 읽기 - 이문제를 맞추는 관건은 몇개의 큐브를 만들건지 빨리 결정하는거 같네여

qhrrkfl2 5년 전 0

내가 가진 n^3개 의 큐브와

한변의 길이가 k개인 정육면체를 만들때 드는 수사위 갯수

즉

n^3 < k^3 인시점을 어떻게 빨리 판별하느냐가 속도문제를 해결하고

문제를 맞추는 원인인데

어떻게 해결해야 할지 감이 안나옵니다.

인덴트가 참 보기 힘들게 나오네여;;;저런방식으로 하면 최악의 경우인 1,000,000^3의 큐브에서 몇개의 큐브를 만들건지 결정하는데에 시간이 너무 오래걸립니다.

어떻게 해야 할까요?

cnt증가량을 점차 올려서 빠르게 수치가 올라가다 너무 큰 값으로 뛰어넘었을때는 역방향으로 다시 내려오는 방식 즉 확률에 기대야 할까요?

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

long long power(long long num, long long square)
{
	long long result = num;
	for (int i = 0; i < square-1; i++)
	{
		result *= num;
	}
	return result;
}
void mycopy(long long *arr, long long *arrend, long long* dest)
{
	int cnt = arrend - arr;
	for (int i = 0; i < cnt; i++)
	{
		dest[i] = *(arr + i);
	}
}

int main()
{
	//    D
	//  E A B F
	//    C
	enum side
	{
		N, A, B, C, D, E, F
	};


	long long input[(side::F)+1] = {1000000,1,2,3,4,5,6};
	//int input[(side::F)+1];

	//for (int i = 0; i < 7; i++)
	//{
	//	std::cin >> input[i];
	//}

	


	long long numOfDice = power(input[side::N], 3);
	long long cnt = 1;
	while (1)
	{
		long long max = power(cnt, 2);
		if (max > numOfDice)
		{
			cnt--;
			break;
		}
		else
		{
			cnt++;
		}

	}
	//2 = 8개
	//1 = 6개
	//3 = 8개

	long long result[8];
	long long maxresult[3];

	mycopy(input + 1, input + 7, result);
	sort(result, result + 6, less<long long>());
	maxresult[0] = result[0];
	
	long long pluscnt = 2;
	long long k = 0;
	for (pluscnt; pluscnt <= 5; pluscnt++)
	{
		result[k] = input[A] + input[pluscnt];
		result[k + 4] = input[F] + input[pluscnt];
		k++;
	}

	sort(result, result + 8, less<long long>());
	maxresult[1] = result[0];

	long long z = 0;
	long long temp[4];
	for (int i = C; i < E; i++)
	{
		result[z] = input[B] + input[i] + input[A];
		result[z + 2] = input[E] + input[i] +input[A];
		result[z+4] = input[E] + input[i] + input[F];
		result[z + 6] = input[B] + input[i] + input[F];
		z++;
	}
	
	sort(result, result + 8, less<long long>());
	maxresult[2] = result[0];

	if(cnt >=3)
	cout << ((((power((cnt - 2), 2)) * 4) + (cnt - 2) * 4 )*maxresult[0]) + ((4+((cnt-2)*8))*maxresult[1]) + (4*maxresult[2]);
	else if (cnt == 2)
	{
		cout << maxresult[2] * 4 + maxresult[1] * 4;
	}
	else
	{
		long long sum = 0;
		for (int i = B; i <= D; i++)
		{
			sum += input[i];		
		}

		long long a = sum + input[A];
		long long b = sum + input[F];
			
		if (a > b)
		{

			cout << a;
		}
		else
		{
			cout << b;
		}
	}

	

	





	return 1;
}

jh05013 5년 전 0

무슨 뜻인지 모르겠습니다. 정육면체의 한 변의 길이는 무조건 N으로 고정되어 있습니다.

qhrrkfl2 5년 전 0

아 문제를 잘못봤네요 감사합니다

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

문제

문제

출처

ICPC

이문제를 맞추는 관건은 몇개의 큐브를 만들건지 빨리 결정하는거 같네여

qhrrkfl2 5년 전 0

jh05013 5년 전 0

qhrrkfl2 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말