문제

https://www.acmicpc.net/problem/2590

---

풀이

크기가 가장 큰 색종이, 크기가 가장 작은 색종이를 같이 붙일 수 있으면 붙이고, 그렇지 않으면 크기가 큰 색종이만 붙이는 식으로 구현하려고 했다. 그런데, 과연 이 방법이 최적해를 보장할 수 있는지 확신이 서지 않았다...

다른 사람 풀이를 참고해보니까... 보드판의 크기가 6으로 고정되어 있기 때문에 모든 경우의 수를 다 따져서 일일이 처리해줘야 하는 문제였다... 이런 유형의 문제는 처음이라 당황스러웠지만,,,, 어렵다기 보다는 귀찮은 문제에 가깝다,,,,

차근차근 하나씩 생각해보자!

size: 6

크기가 6인 색종이는 하나밖에 붙이지 못한다.

size: 5

크기가 5인 색종이는 하나만 붙일 수 있고, 남은 영역에는 크기가 1인 색종이를 최대 36 - 25 = 11 개 붙일 수 있다.

size: 4

크기가 4인 색종이도 하나만 붙일 수 있고, 남은 영역에는 크기가 2인 색종이를 최대 (36 - 16) / 4 = 5 개 붙일 수 있다. 크기가 2인 색종이가 5개보다 적으면, 남은 영역은 크기가 1인 색종이로 채우면 된다.

size: 3

크기가 3인 색종이는 경우의 수가 다양하다. 아래 그림을 보면 바로 이해할 수 있을 것이다.

size: 2

크기가 2인 색종이는 최대 36 / 4 = 9 개 붙일 수 있다.

size: 1

크기가 1인 색종이는 최대 36개 붙일 수 있다.

C++ 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map> 
using namespace std;
typedef pair<int, int> pii; 
typedef long long ll;

int one, two, three, four, five, six;

void input() {
	cin >> one >> two >> three >> four >> five >> six; 
}

void solution() {
	int answer = six;
	
	while(one != 0 || two != 0 || three != 0 || four != 0 || five != 0) {
		while(five > 0){
			int cnt = 36;

			// 크기가 5인 색종이 하나 붙이기 
			five--; 
			cnt -= 25; 

			// 크기가 1인 색종이의 개수 <= 남은 영역 크기 
			if(one <= cnt){
				// 크기가 1인 색종이 모두 붙이기 
				one = 0;
			}else{
				// 크기가 1인 색종이의 개수 갱신 
				one -= cnt;
			}

			answer++; 
		}

		while(four > 0){
			int cnt = 36; 

			// 크기가 4인 색종이 하나 붙이기 
			four--; 
			cnt -= 16; 

			if(two >= 5){
				// 크기가 2인 색종이 5개 붙이기 
				two -= 5; 
				cnt -= 20; 
			}else{
				// 크기가 2인 색종이 모두 붙이기 
				cnt -= two * 4; 
				two = 0; 
			}

			// 크기가 1인 색종이 붙이기 
			if(one <= cnt){
				one = 0; 
			}else{
				one -= cnt; 
			}

			answer++; 
		}

		while(three > 0){
			int cnt = 36; 
			
			if(three >= 4){
				// 크기가 3인 색종이 4개 붙이기 
				three -= 4; 
				cnt = 0;
			}else{
				// 크기가 3인 색종이 모두 붙이기 
				cnt -= three * 9; 
				three = 0; 
			}

			if(cnt == 27){
				if(two >= 5){
					two -= 5;
					cnt -= 20;
				}else{
					cnt -= two * 4;
					two = 0;
				}
			}

			if(cnt == 18){
				if(two >= 3){
					two -= 3; 
					cnt -= 12; 
				}else{
					cnt -= two * 4; 
					two = 0; 
				}
			}

			if(cnt == 9 && two >= 1){
				cnt -= two * 4; 
				two = 0; 
			}

			if(one <= cnt){
				one = 0; 
			}else{
				one -= cnt; 
			}

			answer++; 
		}

		while(two > 0){
			int cnt = 36;

			if(two >= 9){
				two -= 9; 
				cnt = 0; 
			}else{
				cnt -= two * 4; 
				two = 0; 
			}

			if(one <= cnt){
				one = 0; 
			}else{
				one -= cnt; 
			}

			answer++; 
		}

		while(one > 0){
			if(one >= 36){
				one -= 36; 
			}else{
				one = 0; 
			}

			answer++; 
		}
	}

	cout << answer << endl; 
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	input(); 
	solution(); 

	return 0; 
}

일일이 구현하면서도 실수가 생기지 않게 조심!! 해야 하는 문제이다.