[C/C++] 백준 - 12981번 : 공 포장하기

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

12981번: 공 포장하기

문제

빨간 공 R개, 초록 공 G개, 파란 공 B개를 가지고 있다.

오늘은 이 공을 박스로 포장하려고 한다. 박스에는 공이 1개, 2개, 또는 3개 들어갈 수 있다.

박스에 들어가는 공의 색은 모두 다르거나, 모두 같아야 한다.

필요한 박스 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R, G, B가 주어진다. (1 ≤ R, G, B ≤ 100)

출력

첫째 줄에 필요한 박스 개수의 최솟값을 출력한다.

 

---

간만에 풀어보는 그리디 실4 문제인데 생각보다 오래 걸렸다. 맨날 해오던 알고리즘만 풀다가 다른 알고리즘 적용시키려하면 이런다. 꾸준히 다양한 문제 풀어보면서 감을 잡아가야하는데,,

 

공을 포장하는 조건은 2가지가 존재한다.

1. 모두 같은 색의 공을 포장 or 모두 다른 색의 공을 포장
2. 박스에는 공이 1개, 2개, 3개 들어갈 수 있다.

 

우선 제일 먼저 해야할 것은 R, G, B색 공들 모두 3개 이하로 만들어주어야 한다.

ans += R / 3, R %= 3;
ans += G / 3, G %= 3;
ans += B / 3, B %= 3;

위 처럼 박스를 세어주고 모두 3개 이하로 만들어준다. 

 

이 다음에서 좀 헷갈린 것 같아서 시간을 많이 보냈다.

 

순차적으로 박스에 같은 색깔이 몇 개 들어갈 수 있는지 확인하고 넣어주면 된다.

한 박스에 모두 같은 색의 공을 넣는 경우는 제일 마지막이 된다. 왜냐면 어차피 3개 이하로 만들어두었기 때문에 한 박스에 다 때려넣으면 되어서 박스 1개만 추가해주면 된다.

 

1) 색깔이 모두 다른 3개의 공을 한 박스에 넣는 경우

2) 색깔이 2개가 다른 공 2개만 넣는 경우

3) 한 박스에 남은 공 모두 넣어 없애는 경우

 

순으로 코드를 작성해주면 된다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 1e9+3
#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int R, G, B;

void input(){
	cin >> R >> G >> B;
}

int addSameBall(){
	int cnt = 0;
	if(R > 0) cnt++;
	if(G > 0) cnt++;
	if(B > 0) cnt++;
	return cnt;
}

int solution(){
	int ans=0;
	ans += R / 3, R %= 3;
	ans += G / 3, G %= 3;
	ans += B / 3, B %= 3;

	while(R && G && B) ans++, R--, G--, B--;
	while(R && G) ans++, R--, G--;
	while(R && B) ans++, R--, B--;
	while(G && B) ans++, G--, B--;
	ans += addSameBall();
	return ans;
}

int main(){
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}

while문으로 작성하면 되는 걸 재귀로 작성하려고 애쓰다 시간 날렸다. 간단한 코드는 간단하고 빠르게 구현하고 넘어가야하는데 생각이 많아지다보니 코드가 난잡해지고 시간도 오래걸린다. 손코딩으로 어떻게 구현할 지 대충 감은 잡고 구현해야하는 걸 건너뛰어서 그런듯