A4(210mm * 297mm) 용지에 최대한 많은 8cm x 6cm 사진을 뽑으려고 한다.
이 경우 가로로 7장 세로로 4장 총 11장의 사진을 담아 뽑을 수 있다.
이처럼 특정 용지 사이즈가 주어지고, 당신이 뽑고 싶은 사진의 사이즈가 주어질 때
용지 한장에 가장 많은 사진을 담을 수 있는 경우를 출력하시오.
input
210 297
80 60
output
가로 : 7장, 세로 : 4장
4개의 풀이가 있습니다.
def pack(w, h, x, y):
long, short = [w, h] if w>h else [h, w]
pic = [x, y] if x>y else [y, x]
cnt_pack_s = [short//i for i in pic]
cnt_pack_l = [long//i for i in pic]
return max([(i*cnt_pack_s[1], (long-i*pic[0])//pic[1]*cnt_pack_s[0]) for i in range(cnt_pack_l[0]+1)],\
key=lambda x: sum(x))
print(pack(210,297,80,60))
수정
import copy
class pic:
def __init__(self, w, h, x = 0, y = 0):
self._w, self._h = w, h
self.move(x, y)
def move(self, x, y):
self._x = x
self._y = y
self._left = y
self._right = y+self._h
self._top = x+self._w
self._bottom = x
def rotate(self):
return pic(self._h, self._w, self._x, self._y)
def issuperset(self, other): # 사진이 부분집합인지 아닌지 확인
return self._top >= other._top and self._bottom <= other._bottom and\
self._left <= other._left and self._right >= other._right
def isjoint(self, other): # 사진이 겹치는지 아닌지 확인
return self._left < other._right and self._right > other._left and\
self._bottom < other._top and self._top > other._bottom
def __str__(self):
return '({}, {}) - [{}, {}]'.format(self._x, self._y, self._w, self._h)
class paper(pic): # 사직 객체 상속
def __init__(self, w, h):
super().__init__(w, h)
self.pics = [] # 쌓인 사진들
self._xlayer = [0] # 사진 변의 위치 정보
self._ylayer = [0]
def pack(self, obj): # 사진객체 쌓기
if not self.issuperset(obj): return False
for i in self.pics:
if i.isjoint(obj): return False
self.pics.append(obj)
self._xlayer += [obj._top, obj._bottom]
self._ylayer += [obj._left, obj._right]
return True
def unpack(self): # 마지막 넣은 사진 제거
try:
tmp = self.pics.pop()
self._xlayer.remove(tmp._top)
self._xlayer.remove(tmp._bottom)
self._ylayer.remove(tmp._left)
self._ylayer.remove(tmp._right)
except IndexError: pass
if __name__ == '__main__':
# paper_w, paper_h = map(float, input().split())
# pic_w, pic_h = map(float, input().split())
paper_w, paper_h = 210, 297
pic_w, pic_h = 80, 60
base = paper(paper_w, paper_h) # 종이 준비
pics = [pic(pic_w, pic_h), pic(pic_h, pic_w)] # 가로 세로 사진 준비
result = [] # 사진 넣는 순서 결과들
stc_r = [0] # 사진들 가로 세로 정보
stc_ypos = [0] # 마지막 사진 위치
while stc_r:
flag = False
if stc_r[-1] < 2:
_pic = copy.deepcopy(pics[stc_r[-1]])
# 사진을 가로로 나열하다 가득 차면 다음 열을 바꿔주기 위해 ylayer 정보를 ypos 기준으로 소트
tmp = sorted(set(base._ylayer), key = lambda x: x if x >= stc_ypos[-1] else x+paper_h)
for j in tmp:
for i in sorted(set(base._xlayer)):
_pic.move(i, j)
if base.pack(_pic): flag = True; break
if flag: break
if flag:
stc_r[-1] += 1
stc_r.append(0)
stc_ypos.append(_pic._right)
else:
stc_r[-1] += 1
result.append(copy.deepcopy(base.pics))
else:
stc_r.pop()
stc_ypos.pop()
base.unpack()
result = set(tuple(sorted(map(str, i))) for i in result)
max_num_pic = len(max(result, key = lambda x: len(x)))
pos_pic = set(', '.join(i) for i in result if len(i) == max_num_pic)
for i,j in enumerate(pos_pic):
print('\n# ', i+1, ' --- [{0}, {1}]: {2}, [{1}, {0}]: {3}\n'.format(pic_w, pic_h,\
j.count(f'[{pic_w}, {pic_h}]'), j.count(f'[{pic_h}, {pic_w}]')), j, sep = '')
...
...
...
...
# 27 --- [80, 60]: 5, [60, 80]: 6
(0, 0) - [60, 80], (0, 140) - [60, 80], (0, 220) - [80, 60], (0, 80) - [80, 60], (120, 160) - [80, 60], (140, 0) - [60, 80], (140, 80) - [60, 80], (60, 0) - [80, 60], (60, 140) - [60, 80], (80, 220) - [80, 60], (80, 60) - [60, 80]
# 28 --- [80, 60]: 4, [60, 80]: 7
(0, 0) - [80, 60], (0, 120) - [60, 80], (0, 200) - [60, 80], (0, 60) - [80, 60], (120, 160) - [80, 60], (120, 220) - [80, 60], (140, 0) - [60, 80], (140, 80) - [60, 80], (60, 160) - [60, 80], (80, 0) - [60, 80], (80, 80) - [60, 80]
# 29 --- [80, 60]: 4, [60, 80]: 7
(0, 0) - [60, 80], (0, 140) - [60, 80], (0, 220) - [80, 60], (0, 80) - [80, 60], (140, 0) - [60, 80], (140, 160) - [60, 80], (140, 80) - [60, 80], (60, 0) - [80, 60], (60, 140) - [80, 60], (80, 200) - [60, 80], (80, 60) - [60, 80]
# 30 --- [80, 60]: 5, [60, 80]: 6
(0, 0) - [80, 60], (0, 140) - [60, 80], (0, 220) - [80, 60], (0, 60) - [60, 80], (120, 140) - [80, 60], (140, 200) - [60, 80], (140, 60) - [60, 80], (60, 120) - [60, 80], (60, 60) - [80, 60], (80, 0) - [80, 60], (80, 200) - [60, 80]
박범수님 댓글 보고 처음부터 다시 짰습니다
사진을 회전시켜가면서 빈 공간을 찾아 채우는 모든 경우의 수들을 탐색합니다
중복이 많이 나오네요;;
예시의 경우 중복을 필터링하고 난 결과, 최대 11개의 사진을 채우고 30가지의 나열방법이 나오네요
일종의 DFS 입니다
paper에 사진을 0(가로)로 왼쪽 위에 채우고,
다음 0으로 왼쪽 위에 채우고, 다음 0으로 채우고.....
가로가 가득 차면 다음 줄로 넘어가 0으로 채우고, 채우고 채우고....
반복하다 더 이상 채울수 없을때 결과가 저장됩니다[0,0,0,0].
마지막 0을 1(세로)로 고쳐서 채워봅니다. 채워지면 결과 저장[0,0,0,1]
이번에는 한스텝 더 올라가서 [0,0,1] 을 시도해봅니다.
채워지면 다음 0을 넣어 봅니다. [0,0,1,0]...채워지면 또 반복
[1,1,1,1,1,...,1,1] 까지 반복하다 결국 스택이 비워지면 종료합니다
사진을 왼쪽 위에 최적화(?)로 끼워 넣기 위해 xlayer, ylayer 정보를 사용합니다
xlayer, ylayer에는 각 사진의 가로 세로 변의 위치 정보가 저장되어 있습니다
print("input")
paper_x, paper_y = input().split()
paper_x = int(paper_x)
paper_y = int(paper_y)
picture_x, picture_y = input().split()
picture_x = int(picture_x)
picture_y = int(picture_y)
# 가로로 놓을 수 있는 사진의 행/열 수
hor_row_number = paper_y // picture_y # 297 / 60 = 4
hor_column_number = paper_x // picture_x # 210 / 80 = 2
# 세로로 놓을 수 있는 사진의 행/열 수
ver_row_number = paper_y // picture_x # 297 / 80 = 3
ver_column_number = paper_x // picture_y # 210 / 60 = 3
max_picture_number = 0 # 최대 사진 수를 저장
max_case_x = 0 # 최대 사진 수가 나왔을 때 사진의 가로 갯수 저장
max_case_y = 0 # 최대 사진 수가 나왔을 때 사진의 세로 갯수 저장
# i : 가로 형태로 배치한 사진의 행수.
# j : 세로 형태로 배치한 사진의 행수.
for i in range(hor_row_number + 1) :
for j in range(ver_row_number + 1) :
# i 행개의 세로 사진과 j 행개의 가로 사진 배치시, 사진의 세로 길이 계산
total_picture_y = i * picture_y + j * picture_x
# 종이 세로 길이와 사진 세로 길이 비교하여, 종이 길이가 길면 사진 배치 가능하므로, 배치할 수 있는 사진 숫자 계산
if(paper_y >= total_picture_y) :
picture_number = i * hor_column_number + j * ver_column_number
# 최대 사진 수와 비교하여 사진 수가 더 크면 최대 사진 수를 갱신
if(picture_number > max_picture_number) :
max_picture_number = picture_number
max_case_x = i * hor_column_number
max_case_y = j * ver_column_number
print("Output")
print("가로 : %s장, 세로 : %s장" % (max_case_x, max_case_y))
print('용지사이즈입력(mm)')
pglen=int(input('가로:'))
pslen=int(input('세로:'))
print('사진사이즈입력(mm)')
sglen=int(input('가로:'))
sslen=int(input('세로:'))
gcnt1=pglen//sglen
scnt1=pslen//sslen
cnt1=gcnt1*scnt1
gcnt2=pglen//sslen
scnt2=pslen//sglen
cnt2=gcnt2*scnt2
if cnt1 >= cnt2:
print('가로세로 안바꾸고 인쇄 가로:',gcnt1,'세로:',scnt1)
else:
print('가로세로 바꾸어 인쇄 가로:',gcnt2,'세로:',scnt2)
가로와 세로을 바꿀경우 더 많이 찍을수도 있죠. 결과
== RESTART: C:\Users\User\AppData\Local\Programs\Python\Python36-32\test.py == 용지사이즈입력(mm) 가로:210 세로:297 사진사이즈입력(mm) 가로:80 세로:60 가로세로 바꾸어 인쇄 가로: 3 세로: 3
== RESTART: C:\Users\User\AppData\Local\Programs\Python\Python36-32\test.py == 용지사이즈입력(mm) 가로:210 세로:297 사진사이즈입력(mm) 가로:60 세로:80 가로세로 안바꾸고 인쇄 가로: 3 세로: 3
using System;
namespace solution2
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("용지 크기는? ");
string[] input = Console.ReadLine().Split(' ');
Console.WriteLine("사진 크기는? ");
string[] input2 = Console.ReadLine().Split(' ');
int pw = int.Parse(input2[0]), ph = int.Parse(input2[1]);
sortPictures(0, pw, ph, new int[int.Parse(input[0]), int.Parse(input[1])]);
sortPictures(0, ph, pw, new int[int.Parse(input[0]), int.Parse(input[1])]);
Console.WriteLine("\n총 {0}장의 사진을 담아 뽑을 수 있다.", max);
}
public static int max = 0;
private static void sortPictures(int cnt, int pw, int ph, int[,] Arr)
{
for (int r = 0; r <= Arr.GetLength(0)-ph; r++)
{
for (int c = 0; c <= Arr.GetLength(1)-pw; c++)
{
if(isPossible(r, c, pw, ph, Arr))
{
var tmp = copyMap(new int[Arr.GetLength(0), Arr.GetLength(1)], Arr);
for (int x = 0; x < pw; x++)
{
for (int y = 0; y < ph; y++)
tmp[r + y, c + x] = 3;
}
sortPictures(cnt + 1, pw, ph, tmp);
sortPictures(cnt + 1, ph, pw, tmp);
return;
}
}
}
if (cnt > max)
max = cnt;
}
private static int[,] copyMap(int[,] tmp, int[,] Arr)
{
for (int r = 0; r < Arr.GetLength(0); r++)
{
for (int c = 0; c < Arr.GetLength(1); c++)
{
tmp[r, c] = Arr[r, c];
}
}
return tmp;
}
private static bool isPossible(int r, int c, int pw, int ph, int[,] Arr)
{
for (int y = 0; y < ph; y++)
{
for (int x = 0; x < pw; x++)
{
if ( r+y >= Arr.GetLength(0) || c+x >= Arr.GetLength(1) || Arr[r + y, c + x] == 3)
return false;
}
}
return true;
}
}
}