일단 스포당하기 싫은 사람은 뒤로 가기 눌러주셈.
https://www.acmicpc.net/problem/1493
Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net
일단 내 글의 목적은 위 문제의 정당한 풀이를 알고 싶음. 근데 그 풀이를 찾는 과정에서 어이가 없어서 길게 적어본다.
일단 그냥 구글에 "박스 채우기 백준" 이렇게만 검색해도 수많은 블로그 풀이글이 나옴. (열심히 사는 애들 저격하기 싫어서, 그냥 구글 검색해서 보셈)
보통 2가지 풀이로 귀결됨.
가장 큰 블록부터 쓰는 그리디에
1. 분할정복을 섞거나
2. 수학을 섞는
풀이임.
대다수가 자기가 생각한것처럼
큰 것부터 쓰면 좋겠죠? 한번 써보고 분할정복 해봅시다! 루틴임.
일단 첫번째 풀이에서 빠져 있는 가정은, 전체 문제에서 쓸 수 있는 가장 큰 블록을 쓰고, 나눠지는 (3부분 또는 7부분의) 직육면체 부분문제의 해를 합쳐도, 전체 문제해의 1. 존재성, 2. 최소성이 보장된다는 것임. 간단하게만 생각해봐도 3부분의 직육면체를 교차하는 블록을 놓는 해가 있을 수도 있는데 그런건 쌍그리 무시함. 5개 정도 글 읽어봤는데 그거 언급한게 하나도 없음.
두번째 풀이는 차라리 더 양반임. 일단 개요는, 그냥 어떻게 끼울지는 생각 안쓰고 수학적으로 쓸 수 있는만큼 쓰겠다. 이 풀이고, 놀랍게도 통과함.
조금 찾아보니까 질문게시판에 있는 갓-cubelover의 코드를 Python으로 옮긴거였음.
이거 풀이는, 그냥 구글에 "박스 채우기 파이썬" 검색하면 나오는거 보면 됨.
ㅋㅋㅋ 근데 어이없는게 1. 존나 분석한 것처럼 적어놨는데, 정작 잘못 베낌. 2. 그걸 다른 사람들이 베껴가서 똑같이 분석한척하고 틀린 코드를 제출함. 3. 정작 데이터가 약한지 그 틀린 풀이들이 모두 AC 받음 ㅋㅋㅋ
다음 두 코드를 한 번 비교해보셈.
for (i = 19; i >= 0; i--)
w <<= 3;
for w, cnt in cube:
before <<= 3
일단 C++ 코드는 20~0의 모든 A_i를 훑어봄. 그러니까 i가 연속적이여서 그 크기가 8배 곱해지는게 가능함.
문제는 파이썬 코드는 그냥 입력 그대로 받은거여서, w가 연속적이지 않을 수도 있는데 마음대로 가정하고, 그걸 또 이해한것마냥 적어놓음. 8배를 곱하는게 아니라 w의 차이에 3을 곱한걸 비트시프트 해야지 ㅇㅇ
아무튼 2가지 풀이가 모두 Proof-by-ac를 적었던가, 베껴서 양산된걸로 추측함.
그래서 본론: 이거 정당한 풀이 뭐임?
제가 생각하는대로 한번 말해볼게요 그냥 문제 보자마자 떠오르는대로 적는거라 틀릴수도 있어요
관찰 1 : 3차원 문제 - 이 문제가 생각하기 복잡한 이유는 3차원이라는 점인데, 사실 1차원과 비교했을때 그렇게 크게 다른 문제가 아니다. 이유는 천천히 후술함. 일단 핵심은 이 문제를 1차원으로 줄여서 생각해보면 조금 더 이해 및 접근이 쉽다. 그러니 우선 1 * 1 정사각형이 w개 이어 붙어있는데, 1 * 1 정사각형이 2^i개 이어져 있는 직사각형들로 얘를 채우는 문제라고 우선 생각을 해봅시다
그러면 "큰 순서대로 넣는다"는 전략이 제법 합리적이에요. 한번 생각해 봅시다. 길이가 8짜리인 직사각형이 제가 가지고 있고, 4짜리인 직사각형도 제가 가지고 있어요. 이럴 때 굳이 8짜리를 넣을 수 있는데도 불구하고 4짜리를 넣는게 의미가 있을까요? 조금 더 직관을 강화시키기 위해서 예시를 생각해 보면.. 저희는 4가 두개 있다고 생각을 해볼게요. 그럴때 4를 두개다 쓴다면, 반드시 그렇게 하는것보다 그 자리를 8을 대체하는 것이 더 유리할 것입니다. 그렇다면 4를 한개 쓴다고 생각을 해볼게요. 이럴 때에도 마찬가지로 4와 2, 1자투리들을 합치는 것보다 그 자리를 8을 대체하는 것이 유리해요
이렇게 되는 결정적인 이유는 8이 그보다 작은 1, 2, 4, ... 모든 수의 배수이기 때문이에요. 그래서 반드시 더 큰 수를 최대한 채워넣는 전략이 유효한데, 이제 3차원으로 넘어가서 생각해도 동일하게 적용됩니다 왜냐하면 똑같은 이유로 8 * 8 * 8짜리 정육면체 하나 낑겨넣는게 4 * 4 * 4 8개를 낑겨넣든, 더 작은것들을 넣는것보다 항상 더 유리하기 때문에 큰것부터 끼워넣는게 최선이에요
여기까지 나온 시점에서 이 문제는 그리디다 라는 결론에 도달하고, 분할정복은 음 뭔지는 잘 모르겠고 저는 2번풀이 쪽으로 가볼게요 다시 1차원으로 줄여서 생각해보면, 예를 들어서 40짜리 직사각형을 채워 넣는다고 생각해볼게요. 이때 떠올릴 수 있는 그리디 전략 중 하나는, 32 -> 16 -> 8 -> 4 -> 2 -> 1 .. 순으로 직사각형을 보면서, 최대한 넣을 수 있는만큼 채워넣는다는 것이 전략이 됩니다. 실제로 이는 정당하고... 이를 그대로 구현하면 2번 풀이와 완전히 일치하게 됩니다
먼저 화 잔뜩 난 글에 정성 답변 달아줘서 고마워요. 이제 함께 얘기하고 싶은 점은 "왜냐하면 똑같은 이유로 8 * 8 * 8짜리 정육면체 하나 낑겨넣는게 4 * 4 * 4 8개를 낑겨넣든, 더 작은것들을 넣는것보다 항상 더 유리하기 때문에 큰것부터 끼워넣는게 최선이에요" 여기서부터. 이제 w가 2의 거듭제곱꼴이 아니라, 임의의 수면 그 "큰 정육면체 (8x8x8)를 넣어서 만들 수 있는 해가 존재하지 않을 경우, 더 작은 조각만(4x4x4, 2x2x2, 1x1x1)만을 사용한 해도 존재하지 않는다". 이 명제를 증명할 수 있어야 함. 그 증명에 대한 직관이 있을까 궁금하네.
더 첨언하면, 이제 수식 상으로는 더 큰 조각(8x8x8)을 사용했을 지라도, 실제로는 불가능한 경우도 있을 수 있음. 이런 경우가 없는 것이 증명되는가?도 있겠음.
음.. 우선 이렇게 생각해볼게요. 대충 13*13*13짜리 정육면체가 있는데, 여기에서 4*4*4와 2*2*2, 1*1*1은 충분히 많이 있는 상황인데, 이때 8*8*8을 쓰지 않는것이 최선이다. 라고 가정해봅시다. 이때 확인할 수 있는게, 4*4*4와 2*2*2, 1*1*1을 적절히 위치를 잘 조정하면, 가장 앞을 8*8*8이 꽉 차도록 순서를 변경할 수가 있어요. 이거는 1차원에서 생각을 해보면, 13을 4 + 2 + 4 + 2 + 1, 이런 식으로도 채울 수는 있지만, 알아서 임의로 순서를 바꿔서, ex) 4 + 4 + 2 + 2 + 1 가장 앞에서부터 합치면 8이 나오도록 바꿀 수 있어요. 사실 그냥 내림차순으로 정렬하면 됩니다. 이렇게 되면, 결국 어떤 w에 대해서도, 가장 앞이 8*8*8과 같고
지금 채워넣은 4*4*4, 2*2*2, 1*1*1쌍을 그냥 그 위치에 8*8*8로만 대체하면 더 좋은 전략이라고 말할수가 있게돼요
8x8x8를 블록 상에서 '쓰는게 가능한데도' 쓰지 않는 해가 있을 경우, 이를 적당히 쉬프트해서 "8x8x8 자리를 만들 수 있다." 이 lemma를 증명하는게 가능하면 위 모든 논제가 성립되긴 함. 그러면 이게 정육면체이므로 분할정복 풀이, 수학적 풀이도 얼추 맞게 되지.
그 쉬프트한다는게 좀 엄밀하지 않은 부분이라 생각함.
확실히 엄밀하게 말하기는 좀 어려울듯 하네요. 음.. 와닿을지는 모르겠는데 모든 정육면체를가장 큰거를 앞에 두도록, 내림차순으로 만들면 항상 만족하기는 합니다 ex) 13 = 4 + 4 + 2 + 2 + 1 // 13 = 4 + 2 + 2 + 2 + 2 + 1 // 등등, 어떤 식으로 채워나가든 내림차순이기만 하면 가장 앞의 합이 2^i꼴이 만들어질거에요
내림차순이라는게, 구석부터 하나씩 채워넣겠다는 이야기일까요? 1차원은 사실 동전채우기 문제랑 동일하니까 여기서 좋은 예시는 아님.
네네 가장 왼쪽 아래 구석부터 채워넣는거에요. 어떤 식으로든 8*8*8를 안쓰겠다고 하면, 4*4*4와 2*2*2와 1*1*1의 개수가 결정이 될거 아니에요? 그걸 가지고, 4*4*4부터 가장 왼쪽 아래 구석부터 아무렇게나 채워 넣어가면 결국 어떤식으로 채워넣든 가장 왼쪽아래 8*8*8을 봤을 때 정확히 메워지게 됩니다
모든 숫자가 앞 숫자의 배수일 때에는 1차원과 3차원이 동일하다는 직관을 형성하는게 중요한 부분인것 같아서 굳이 1차원에서 계속 얘기를 했습니다
1차원에서 생각하는것 + 구석부터 채워넣는게 참 괜찮은 직관이긴 한데, 저한테는 그렇게 자명하게 느껴지지는 않네요. 혹시 2차원에서 동일한 문제로 이야기를 이어갈 수 있을까요? 그 Lemma가 성립한다면 N차원에서도 성립할 것 같다는 생각이 듭니다.
모든 정사각형 한 변의 길이가 2의 지수라는게 여기서의 중요한 조건인데, 여기서도 동일하게 "작은 정사각형을 fitting하는 해를 적당히 배열해서 큰 정사각형 하나가 온전히 들어가도록 만들 수 있다"가 같은 Lemma가 되겠죠.
굳이 2차원으로 내리는 이유는, 3차원이여서 엄밀한 사고에 조금 방해를 주는 것 같아서 차원을 내립니다.
네네 N차원에서도 성립합니다. 그럼 2차원에서 생각해볼게요. 13 * 13을 채워넣는데 4 * 4, 2 * 2, 1 * 1을 가지고 4*4부터 왼쪽아래에 다 밀어넣고, 그 다음부터는 2*2만 써서 왼쪽아래에 쓰고, 마지막으로 1*1만 써서 나머지를 채워보세요. 한번 직접 해보시는게 도움이 될 것 같습니다
엄밀한 증명은 저도 증명론을 잘 알지는 못해서 도움이 못될것 같습니다. 직접 해보시는게 ps에서는 가장 좋은 방법이지 않을까 싶습니다
오.. 모든 수가 자기 이하 수의 배수이므로 어떤 해를 가져오든 왼쪽 아래부터 차례로 채워가면 자기보다 큰 배수의 정사각형을 만든다."로 정리되네. 3차원도 마찬가지고. 결국 그리디하게 어떤 해든 "왼쪽 구석에서 큰 것부터 잘 모아보면 그것보다 큰게 하나 생긴다"로 요약할 수 있겠네. ㄳㄳ 이해 끝.
그러면 비슷한 방식으로 N차원에서는 각 축에 대해 성립하고. 역시 고수.
큰 정육면체를 쓰는 해가 존재하지 않으연 작은 정육면체를 쓰는 해도 존재하지 않는다 -> 작은 정육면체를 쓰는 해가 존재한다면 큰 정육면체를 쓰는 해도 존재한다니까 해의 존재성은 증명되고, 배수 관계만 있는 동전문제처럼 그리디를 증명할 수 있으니 최소성도 증명될 듯