문제 출처:https://www.acmicpc.net/problem/2590


 문제


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

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

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


 입력


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


 출력


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


가장 큰 색종이부터 판에 붙여주면서 남는 공간에도 들어갈수 있는 가장 큰 색종이를 넣어주는 식으로 문제를 풀었습니다. 


판의 크기가 크지 않고 색종이의 종류도 얼마 안되어서 경우의 수를 전부 계산하여 그림으로 나타내면 


일단 6번 색종이는 판에 꽉 차므로 다른 색종이를 더 넣을 수 없습니다.


5번 색종이는 



위와같이 1개만 들어갈 수 있고 나머지 공간은 전부 1번 색종이로 채울 수 있습니다.



4번 색종이는


위와같이 1개만 들어갈 수 있고 나머지 공간에 2번 색종이가 최대 5개 들어갈 수 있습니다.


2번 색종이가 5개 이하라면 나머지 공간엔 1번 색종이로 채워주면 됩니다.




3번 색종이가 경우의 수가 여러가지 있는데



이렇게 전부 3번 색종이로만 채워진다면 최대 4개가 채워집니다.



3번 색종이가 3개만 채워진다면 나머지 공간에 2번색종이가 1개 들어갈 수 있고


나머지 공간은 1번 색종이로 채워줍니다.



3번 색종이가 2개만 채워진다면 2번 색종이는 최대 3개 채워지고 


나머지 공간은 1번 색종이로 채워줍니다.



3번 색종이가 1개만 채워지면 2번 색종이는 최대 5개 채워지고


마찬가지로 남는 공간은 1번 색종이로 채워줍니다.


2번 색종이는



위와같이 최대 9개까지 채울 수 있습니다.


남은공간이 있다면 1번 색종이로 채우면 됩니다.



위와같은 과정을 거치고도 1번 색종이가 남아있다면 한판에 최대 36개가 들어갈 수 있으니 


남아있는 1번 색종이의 수에 맞춰 판을 추가해줍니다.



이런방식으로 주어진 색종이에서 최소 몇개의 판이 필요한지 구할 수 있습니다. 


아래는 전체 소스입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <string.h>
#include <limits>
 
using namespace std;
int n, l, r, **arr, **area, dp[2501], sum = 0, cnt = 0;
 
int main()
{
    int one, two, three, four, five, six;
    cin >> one >> two >> three >> four >> five >> six;
    int count = 0;
    count += six;
    while (one != 0 || two != 0 || three != 0 || four != 0 || five != 0)
    {
        while (five>0)
        {
            int pan = 36;
            five--;
            pan -= 25;
            if (one <= pan)
                one = 0;
            else
                one -= pan;
            count++;
        }
        while (four>0)
        {
            int pan = 36;
            four--;
            pan -= 16;
            if (two>5)
            {
                two -= 5;
                pan -= 20;
            }
            else
            {
                pan -= 4 * two;
                two = 0;
            }
            if (one <= pan)
                one = 0;
            else
                one -= pan;
            count++;
        }
        while (three>0)
        {
            int pan = 36;
            if (three>4)
            {
                three -= 4;
                pan = 0;
            }
            else
            {
                pan -= 9 * three;
                three = 0;
            }
            if (pan == 27 && two>5)
            {
                two -= 5;
                pan -= 20;
            }
            else if (pan == 27 && two <= 5)
            {
                pan -= 4 * two;
                two = 0;
            }
            if (pan == 18 && two>3)
            {
                two -= 3;
                pan -= 12;
            }
            else if (pan == 18 && two <= 3)
            {
                pan -= 4 * two;
                two = 0;
            }
            if (pan == 9 && two >= 1)
            {
                pan -= 4 * two;
                two = 0;
            }
            if (one <= pan)
                one = 0;
            else
                one -= pan;
            count++;
        }
        while (two>0)
        {
            int pan = 36;
            if (two>9)
            {
                two -= 9;
                pan = 0;
            }
            else
            {
                pan -= 4 * two;
                two = 0;
            }
            if (one <= pan)
                one = 0;
            else
                one -= pan;
            count++;
        }
        while (one>0)
        {
            if (one>36)
                one -= 36;
            else
                one = 0;
            count++;
        }
    }
    cout << count << endl;
    return 0;
}
cs



저작자표시

'알고리즘 문제 > 시뮬레이션' 카테고리의 다른 글

[백준] 14890번: 경사로 - C++  (0) 2018.07.27

+ Recent posts

티스토리툴바