글 읽기 - 반례좀 찾아주세요 ㅠㅠ...

wxogus25 6년 전 0

가로, 세로, 높이중 가장 작은것을 찾은 다음, 그 길이의 최상위 비트를 구해

그 크기만큼의 박스로 채울 수 있는 최대한의 부피를 채웁니다. (27 ~ 29)

그 후, 남은 부피를 7등분해 재귀호출하는 방식으로 fill 함수를 만들었습니다.

메인 함수 부분은 상자를 채울 수 있는 최소한의 박스 수를 구하면서

주어진 박스로 상자를 채울 수 있는지 없는지 검사합니다.

예제도 잘 통과했는데 어디서 틀린걸까요??

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <deque>
#include <functional>

using namespace std;

long long got[21];
long long ned[21], mul;

void fill(int a, int b, int c)
{
	int d[3] = { a,b,c };
	sort(d, d + 3);
	int x = d[0], y = d[1], z = d[2];
	if (x == 0) return;
	for (int i = 19; i >= 0; i--)
	{
		if (x&(1 << i))
		{
			ned[i] += (y / (1 << i)) * (z / (1 << i));

			fill(x % (1 << i), (1 << i), (1 << i));
			fill(z % (1 << i), (1 << i), (1 << i));
			fill((1 << i), z % (1 << i), x % (1 << i));
			fill(y % (1 << i), (1 << i), (1 << i));
			fill(y % (1 << i), z % (1 << i), (1 << i));
			fill(y % (1 << i), x % (1 << i), (1 << i));
			fill(y % (1 << i), z % (1 << i), x % (1 << i));
			return;
		}
	}
}

int main()
{
	int a, b, c;
	long long dap = 0;
	cin >> a >> b >> c;
	int n, q, w;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> q >> w;
		got[q] = w;
	}
	fill(a, b, c);
	for (int i = 19; i >= 0; i--)
	{
		dap += min(ned[i], got[i]);
		ned[i] = max((long long)0, ned[i] - got[i]);
		if (ned[i] > 0)
		{
			if (ned[i] > 1000000 || i == 0)
			{
				cout << -1;
				return 0;
			}
			else
			{
				ned[i - 1] += ned[i] * 8;
				ned[i] = 0;
			}
		}
	}
	cout << dap;
}

kdk8361 6년 전 1

1000000 1000000 1

을 입력하니 ned[0]에 쓰레기 값이 들어가네요. 29번째 줄을 약간 수정하니 제대로 답이 들어갑니다.

wxogus25 6년 전 1

조언 감사합니다!

말씀하신 쓰레기 값의 원인이 자료형 때문이 맞나요? 수정하고 제출했는데 틀렸다고 하네요 ㅠㅠ

kdk8361 6년 전 1

54 42 58
0

를 입력하니 제 코드에서는

[0] 0
[1] 1883
[2] 140
[3] 66
[4] 10
[5] 1

이렇게 나오네요. 코드 돌려보니 결과가 좀 다르게 나옵니다.

wxogus25 6년 전 1

감사합니다!

다시 확인해보니 31~37 까지 재귀호출 부분의 로직에 문제가 있었네요

fill(x % (1 << i), (y / (1 << i))*(1 << i), (z / (1 << i))*(1 << i));
fill(z % (1 << i), (x / (1 << i))*(1 << i), (y / (1 << i))*(1 << i));
fill(y % (1 << i), (x / (1 << i))*(1 << i), (z / (1 << i))*(1 << i));
fill(y % (1 << i), z % (1 << i), (x / (1 << i))*(1 << i));
fill(x % (1 << i), z % (1 << i), (y / (1 << i))*(1 << i));
fill(x % (1 << i), y % (1 << i), (z / (1 << i))*(1 << i));
fill(y % (1 << i), z % (1 << i), x % (1 << i));

이렇게 하니까 답이 나오네요

덕분에 두달전의 복수(?)를 할 수 있었습니다. 감사합니당~!

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

문제

문제

출처

ICPC

반례좀 찾아주세요 ㅠㅠ...

wxogus25 6년 전 0

kdk8361 6년 전 1

wxogus25 6년 전 1

kdk8361 6년 전 1

wxogus25 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말