글 읽기 - 어째서 이런 풀이가 되는지 모르겠습니다.

dahyun1226 4년 전 1

아래 코드는 cubelover님의 코드입니다(주석 조금 더한 것)

어찌어찌 해석은 됩니다만, 왜 남은 부분의 모양을 고려하지 않아도 되는지 모르겠습니다.

단순하게 생각해서는 큐브모양 빼고 나서 8부분중 7부분으로 재귀 돌려야 할 것 같은데 말이죠.

모양을 고려하지 않아도 된다는 그 증명을 못하겠습니다...

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <unordered_map>
#define MOD 1000000007
#define MAXINT 2000000000
#define mp make_pair
using namespace std;

int a[20];

int main() {
	long long w = 0;
	int t, x, y, z, r = 0;
	int i, n, u, v;
	scanf("%d%d%d%d", &x, &y, &z, &n);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &u, &v);
		a[u] += v;
	}
	for (i = 19; i >= 0; i--) {
		w <<= 3; //이미 공간 차지한 부분 갯수 8배 늘리기
		t = min((long long)a[i], (long long)(x >> i) * (y >> i) * (z >> i) - w);
		w += t; // 새롭게 공간 차지한 부분 더해주기
		r += t; // 총갯수
	}
	printf("%d", w == (long long)x * y * z ? r : -1);
//부피 딱 되면 -1
}

alexroh 3년 전 0

1년 전 질문이지만 공부할 겸, 틀리면 다른 분들에게 지적도 받을 겸 써봅니다.

저 코드는 모양을 고려하지 않고 철저히 개수로만 접근하고 있습니다.

남은 부분의 모양을 고려하려면 코드 내에 모양을 만드는 부분이 있어야 하는데, 그런 게 없고 오직 개수를 카운팅하는 부분뿐입니다.

다시 말해, 남은 부분의 모양은 고려할 필요가 없는 접근 방식입니다. 필요한 것은 이미 채운 부분의 개수만큼 빼는 것인데, 그건 코드에서 해결해주고 있습니다.

dahyun1226 2년 전 0

시간이 많이 지났지만, 혹시나 다른분들께 힌트가 될까바 댓글을 쓰자면,

넣어주는 큐브가 이전에 넣은 큐브를 2*2*2로 채울수 있기 때문에 이전에 넣은 큐브를 신경쓰지 않은게 가능했던 것 같습니다.

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

문제

문제

출처

ICPC

어째서 이런 풀이가 되는지 모르겠습니다.

dahyun1226 4년 전 1

alexroh 3년 전 0

dahyun1226 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말