[ Baekjoon - 11/13 ] - 2590번: 색종이

• 문제 링크 : https://www.acmicpc.net/problem/2590

2590번: 색종이

 

• 소요 시간 : 2시간

색종이 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

3658

670

554

23.064%

문제

<그림 1>과 같이 정사각형 모양을 한 여섯 종류의 색종이가 있다. 1번 색종이는 한 변의 길이가 1cm이고, 차례대로 그 길이가 1cm씩 커져, 6번 색종이의 한 변의 길이는 6cm가 된다.

<그림 1>

주어진 색종이를 <그림 2>와 같이 가로, 세로의 길이가 각각 6cm인 판 위에 붙이려고 한다. 색종이를 붙일 때는 색종이가 판의 경계 밖으로 삐져 나가서는 안되며, 색종이가 서로 겹쳐서도 안 된다. 또한 하나의 색종이는 하나의 판에만 붙여야 한다.

<그림 2>

각 종류별로 색종이의 장수가 주어질 때, 그 색종이를 모두 붙이기 위해서 위와 같은 판이 최소 몇 개가 필요한지 구하는 프로그램을 작성하시오.

입력

첫째 줄부터 여섯째 줄까지 각 종류의 색종이의 장수가 1번부터 6번까지 차례로 주어진다. 각 종류의 색종이의 장수는 최대 100이다.

출력

첫째 줄에 필요한 판의 최소 개수를 출력한다.

예제 입력 1 복사

5
3
0
1
1
0

예제 출력 1 복사

2

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 128MB
   • 문제
     
     • 1~6번의 색종이 수가 입력된다. 각 색종이의 수는 100장이내
     • 6종류의 색종이는 각각 1x1, 2x2, 3x3, ..., 6x6 크기의 정사각형 모양의 색종이
     • 위 색종이를 이용해 6x6판을 채우면 되는데 최소 몇개의 판을 채울 수 있는지 출력하는 문제
     • 여기서 중요한 것은, 하나의 색종이는 하나의 판에만 붙어야한다는 조건이다... 이걸 놓쳐서 많이 돌아갔음 ㅠ
   • 이해
     • 위에서 언급한 마지막 조건을 간과하여... 판을 어떻게 붙여야 많이 붙일 수 있는지 부터, 판 연결부분도 붙을 수 있으려면 어떤식으로 체크를 해줘야할지 고민했다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 문제 이해를 위한 그림은 그려보지 않았음.. 그렸다면 덜 돌아갔으려나..
3. 문제를 어떻게 해결할 것인가
   • 모든 시도는 사실상 그리디인데, 구현을 어떤식으로 할지 많이 고민했어서 이를 나눠 적어보고자한다.
   • 그리디라고 생각한 이유는, 다 같은 정사각형인데 면적만 다르고 한정된 판에 채워야하는 문제였기 때문
   • 필자가 겪어본 그리디 문제들처럼 단순히 정렬하고 큰 기준을 잡아 조건한두번 나누는 문제가 아닌 분기가 너무 많아서 오래 고민했다...(；′⌒`)
   • 1st 접근 - 정사각형을 하나 맵에 넣었을때 생길 수 있는 구조로 분석)

     • 

     • 각 정사각형의 한변의 길이에 따라 1개 넣었을때 , 보다작은 정사각형이 몇개 들어갈 수 있는지 분석해보았다.
     • 6x6짜리 정사각형은 고민없이 각 판 1개씩으로 계산하면 되므로 간단했음
     • 5x5는 1x1짜리 11개만 들어와야 가능
     • 4x4는 2x2짜리 5개와 1x1짜리 20개 사이에서 적절히 섞어서 가져와도 가능
     • 3x3는 4개 넣으면 맵이 다 채워지는데, 이때부터 좀 많이 고민했음..
       이걸 다적어 말아 를 꽤 고민하다가 가장 큰 숫자만 넣기로 결정함
     • 2x2는 좀더 난해해졌는데..
       여기서 가장 큰값만 적겠다하고 내려온 시점이라 딜레마에 빠져버림..
     • 다르게 접근하고자 했다.
   • 2nd 접근 - 각 공간이 1x1~6x6 등장했을 때 어떻게 넣을 수 있을지)

     • 

     • 1x1은 [1x1]밖에 넣지 못하고
       2x2는 [2x2 1개] or [1x1 4개]가능
       3x3은 [3x3 1개] or [2x2 1개 + 1x1 5개] or [1x1 9개]
       4x4는 [4x4 1개] or [3x3 1개 + 1x1 7개] or [2x2 4개] or [1x1 16개]
       ......
     • 여기서도 이걸 어떻게 연계시키지 하며 오래 고민을 했지만 내 구현력으로는 모자람을 느껴 결국 다른 분의 코드를 참고했음
   • 3rd 접근 - 크게 가장 큰 사각형이 6x6, 5x5, ... 2x2로 분기를 나눈뒤 개수를 고려)

     • 

     • 다른 분들의 코드를 살짝 구경했는데 분기점을 나눌 때 가장 큰 정사각형을 넣어야한다면, 개수를 그때 고려해서 분기를 나눠주는 방식으로 구현한코드가 대부분이었다.
     • 그래서 스스로 다시 생각해보며 끄적이며 위와같은 결과를 얻었고 코드로 구현할 수 있었다!
     • 사실 그려놓고도 코드적으로 어떻게 풀어쓸지 고민을 상당히 많이했고, 혼자했으면 4시간은 잡아먹었을 문제라고 생각된다ㅠ
4. 위 계획을 검증
   • 검증.... 사실상 정사각형이라 좀 간단했던 것 같긴하다. 쉽다는 말은 절대 아님..
   • 정사각형이 아니었다면 회전이나 생긴모양을 고려해서 넣어야하므로, 아마 완탐정도여야 풀 수 있을거라 생각하지만 그마저도 구현이 가능할지 감은 잘 안잡힌다.
   • 무튼 돌아와서, 위에서도 언급한 중요한 문제조건인 "하나의 색종이는 하나의 판에만 붙여야 한다." 때문에 가장 큰 정사각형을 넣는 식으로 구현하면 분기만 잘 따져주고 코드적으로 잘 풀어내면 되는 문제가 된다.
   • 분기는 위에서 언급했으므로 생략하겠음
5. 계획 수행 (실제코드 작성)
   1. Java 11

      1. import java.util.*;
         import java.io.*;
         
         public class Main{
             public static int ans, r, d;
             public static int[] num;
         
             public static void main(String[] args) throws IOException {
                 //System.setIn(new FileInputStream("src/input.txt"));
                 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
                 num = new int[7];
                 for(int i = 1; i <= 6; i++) {
                     num[i] = Integer.parseInt(br.readLine());
                 }
         
                 // 그리디적 접근 - 큰 정사각형부터 넣기
                 // 1. 6x6은 판 하나 차지
                 ans += num[6];
         
                 // 2. 5x5
                 // => 5x5 1개 + 1x1 11개
                 ans += num[5];
                 num[1] -= num[5]*11;
         
                 // 3. 4x4
                 // => 4x4 1개 + 2x2 5개
                 // => 4x4 1개 + 1x1 20개
                 // 4x4 1개를 채우고 남은 면적 20에서 2x2와 1x1 섞어도 O
                 ans += num[4];
                 for(int i = 0; i < num[4]; i++) {
                     r = 20;
                     while(r > 0) {
                         if(num[2] > 0) {
                             r = r-4;
                             num[2]--;
                         }else if(num[1] > 0) {
                             r = r-1;
                             num[1]--;
                         }else {
                             r = 0;
                         }
                     }
                 }
                 // 4. 3x3
                 // => 3x3 4개
                 // => 3x3 3개 + 2x2 1개 + 1x1 5개
                 // => 3x3 2개 + 2x2 3개 + 1x1 6개
                 // => 3x3 1개 + 2x2 5개 + 1x1 7개
                 // 3x3을 채우고 남은 면적에서 2x2와 1x1 섞어도 O
         
                 // 3x3이 4개이상이면 판 최대한 채움
                 while(num[3]/4 > 0) {
                     num[3] = num[3]-4;
                     ans++;
                 }
         
                 // 3x3 판으로 6x6판들을 채웠을때 남은영역의 개수를 구하기
                 if(num[3] == 3) {
                     ans ++;
                     r = 9;
                     d = 1;
                 }else if(num[3] == 2) {
                     ans ++;
                     r = 18;
                     d = 3;
                 }else if(num[3] == 1) {
                     ans ++;
                     r = 27;
                     d = 5;
                 }else {
                     r = 0;
                     d = 0;
                 }
         
                 // 남은 영역만큼 2x2와 1x1로 채우기
                 if(r > 0) {
                     while(d > 0) {
                         if(num[2] > 0) {
                             d--;
                             r = r-4;
                             num[2]--;
                         }else {
                             d = 0;
                         }
                     }
         
                     while(r > 0) {
                         if(num[1] > 0) {
                             r --;
                             num[1]--;
                         }else {
                             r = 0;
                         }
                     }
                 }
         
                 // 5. 남은 2x2와 1x1로 맵채우기
                 r = 0;
                 while(num[2] > 0 || num[1] > 0) {
                     if(r == 0) {
                         ans++;
                         r = 36;
                     }else {
                         if(num[2] > 0) {
                             r = r-4;
                             num[2]--;
                         }else {
                             r = r-1;
                             num[1] --;
                         }
                     }
                 }
         
                 bw.write(ans+"\n");
                 bw.flush();
             }
         }

6. 회고하기
   • 조금이지만 필자 코딩실력이 상승했다고 생각했었는데.. 결국 누가 검증 확실하게 다 해둔 자료구조나 유명한 알고리즘 얻어먹기 수준이었다고 생각된다.. 빡구현문제만 나오면 처참히 깨지고있으니ㅠ
   • 빡구현문제 중심으로 풀면서 내 생각을 넓혀가며 솔루션을 찾아가는 방법을 익혀야할듯하다..

 

• 결과