[C++] 백준(BOJ) - 3687 : 성냥개비
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.
성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)
출력
각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다.
알고리즘
- DP
- 그리디
풀이
- 문제 범위
- 1 < n < 101
- 성냥개비로 1을 붙여나갈 때(2개 소모) 50자리 수가 나온다
- int형 10자리수가 최대
- long long형 20자리수가 최대
- string 기반으로 문제풀이
- 최대값
- 그리디
- 자리수가 최대이면 최대값이다
- n의 개수 짝수 : 1로만 자리수를 채울 수 있다 (2개 소모)
- n의 개수 홀수 : 7(3개 소모) + 1로만 채우기 (최대 자리수)
- 그리디
- 최소값
- 모든 경우의 수 찾아야 함
- DP 활용
- Botton-up
- dp배열을 0에서부터 만들어 나가며 최소값을 string dp배열에 갱신
- 큰 자리수부터 최소값을 넣고, 끝자리에 최소값을 더해가는 방법
- Top-down
- 우선 0~9까지를 붙이기
- 남은 성냥(here - a[i])을 넘겨가며 최소값을 만들어내기
- 예외처리
- 맨 앞자리에 0이들어가는 경우의 수 빼주기
코드 1 : Bottom-Up
// BOJ - 3678 : 성냥개비
#include<bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int t, n;
int a[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
string dp[104], max_str = "111111111111111111111111111111111111111111111111119";
string get_min_str(string a, string b)
{
if (a.size() == b.size()) return (a < b ? a : b); // 스트링의 비교는 선 사이즈 체크 필수
if (a.size() < b.size()) return a;
return b;
}
string findMax(int here)
{
string res = "";
if (here & 1) // here이 홀수인 경우 7 붙이기
{
res += '7';
here -= 3;
}
while (here)
{
res += '1';
here -= 2;
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
fill(dp, dp + 104, max_str);
// 1. 바텀업 방식
dp[0] = "";
for (int i = 2; i < 104; i++)
{
for (int j = 0; j <= 9; j++)
{
if (i - a[j] < 0) continue; // 남은 성냥개비 수보다 사용하려는 수가 드는 성냥개비가 적으면 x
if (j == 0 && dp[i - a[j]] == "") continue; // 성냥개비가 6개가 남았고 맨앞의 인덱스에 0이 들어가는 경우이면
dp[i] = get_min_str(dp[i], dp[i - a[j]] + to_string(j));
}
}
while (t--)
{
cin >> n;
cout << dp[n] << " " << findMax(n) << '\n';
}
return 0;
}
코드 2 : Top-Down
// BOJ - 3678 : 성냥개비
#include<bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int t, n;
int a[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
string dp[104], max_str = "111111111111111111111111111111111111111111111111119";
string get_min_str(string a, string b)
{
if (a.size() == b.size()) return (a < b ? a : b); // 스트링의 비교는 선 사이즈 체크 필수
if (a.size() < b.size()) return a;
return b;
}
// 2. 탑다운 방식
string findMin(int here)
{
if (here == 0) return "";
string& res = dp[here];
if (res != max_str) return res;
for (int i = 0; i <= 9; i++)
{
if (here - a[i] < 0) continue;
if (here == n && i == 0) continue; // 성냥개비 모두 썼을때, 첫번째 인덱스가 0인 경우 불가능
res = get_min_str(res, to_string(i) + findMin(here - a[i]));
}
return res;
}
string findMax(int here)
{
string res = "";
if (here & 1) // here이 홀수인 경우 7 붙이기
{
res += '7';
here -= 3;
}
while (here)
{
res += '1';
here -= 2;
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
while (t--)
{
cin >> n;
fill(dp, dp + 104, max_str);
cout << findMin(n) << " " << findMax(n) << '\n';
}
return 0;
}
평가
- 한문제에서 그리디와 DP를 어떨 때 사용해야하는지 파악하고 풀이할 수 있다
- Bottom-Up과 Top-Down 두 방식으로 DP를 풀어내고, string 형의 dp값을 리턴하여 대소비교를 하는 것까지 총망라된 좋은 문제
