시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 745 | 230 | 95 | 22.248% |
DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태로 이루어져 있다. 각 격자는 정사각형 모양이며, 퍼즐 조각이 있을 수도 있고, 없을 수도 있다. 즉, 아래 그림도 올바른 퍼즐의 완성 형태이다.
성공적으로 DIY가 끝나서 퍼즐이 2개가 완성되었는데, 보관해야 하는 액자를 아직 구매하지 않았다. 그 이유는, 호석이는 엄청난 짠돌이기 때문에 퍼즐 하나마다 액자 하나를 사는 것은 상상도 못하기 때문이다. 액자의 가격은 액자의 넓이(행의 개수 × 열의 개수) 로 결정된다. 즉, 퍼즐 두 개를 퍼즐 조각끼리 같은 격자에서 만나지 않도록 배치해서 하나의 액자에 담는 방법 중에 가장 적은 비용일 때를 찾아보자! 단, 각 퍼즐은 90도, 180도, 270도로 자유롭게 회전시켜도 된다.
첫 줄에 퍼즐의 크기를 나타내는 N1, M1이 공백으로 구분되어 주어진다. 이어서 N1개의 줄에 걸쳐서 완성된 첫 번째 퍼즐의 정보가 주어진다. 각 행마다 M1개의 0 또는 1이 공백없이 주어진다. 다음 줄에 퍼즐의 크기를 나타내는 N2, M2이 공백으로 구분되어 주어진다. 이어서 N2개의 줄에 걸쳐서 완성된 두 번째 퍼즐의 정보가 주어진다. 각 행마다 M2개의 0 또는 1이 공백없이 주어진다. 0이 써있는 격자는 퍼즐 조각이 없는 격자이며 1은 있는 격자이다. 두 퍼즐 모두 4개 모서리에 최소 하나의 1은 존재하는 것이 보장된다.
두 개의 퍼즐을 담을 수 있는 액자들 중에 최소 넓이를 출력한다.
5 5 11111 10000 11111 10000 11111 5 3 101 101 101 101 111
30
2번 블록을 반시계 방향으로 90도 회전시 뒤에 합치면
111110
122222
111112
122222
111110
으로 합쳐진다. 여기서 1은 첫 번째 퍼즐의 조각, 2는 두 번째 퍼즐의 조각, 0은 빈 칸이다. 이것보다 작은 넓이는 없다.
4 4 1001 0100 1011 1110 4 4 1000 0010 1101 0110
16
Contest > 류호석배 알고리즘 코딩 테스트 > 제2회 류호석배 알고리즘 코딩 테스트 3번