[백준 3687번 C/C++] 성냥개비

 

[백준 3687번 C/C++] 성냥개비

 

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

3687번: 성냥개비

---

 

 

해결전략

 

구현

동적계획법 Dynamic Programming, DP

 

---

 

정답코드

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int t; // 테스트 케이스의 개수
int n; // 성냥개비의 개수
// int num[10] = { 2, 5, 5, 4, 5, 6, 3, 7, 6, 6 }; // 각 숫자를 만드는데 필요한 성냥개비의 개수

string MinNum(int x){
    // 기본적으로 성냥개비 2~13개로 만들 수 있는 가장 작은 숫자들을 직접 반환
	if (x == 2) return "1";
	else if (x == 3) return "7";
	else if (x == 4) return "4";
	else if (x == 5) return "2";
	else if (x == 6) return "6";
	else if (x == 7) return "8";
	else if (x == 8) return "10";
	else if (x == 9) return "18";
	else if (x == 10) return "22";
	else if (x == 11) return "20";
	else if (x == 12) return "28";
	else if (x == 13) return "68";

    // 성냥개비가 14개 이상인 경우
	int a = x / 7;   // 7개짜리 숫자(8)를 최대한 많이 만들기
	int b = x % 7;   // 나머지 성냥개비 개수

	string minNum = "";
	if (b == 0) {
		while (a--) {
			minNum = minNum + "8"; // 나머지가 없으면 8만으로 구성
		}
	}
	else {
        // 나머지가 있을 경우, 최소 숫자를 만들기 위한 로직
		a--;
		if (b == 1) {
			while (a--) {
				minNum = minNum + "8";
			}
			minNum = "10" + minNum; // 나머지가 1개일 때
		}
		else if (b == 2) {
			while (a--) {
				minNum = minNum + "8";
			}
			minNum = "18" + minNum; // 나머지가 2개일 때
		}
		else if (b == 3) {
			a--;
			while (a--) {
				minNum = minNum + "8";
			}
			minNum = "200" + minNum; // 나머지가 3개일 때, 특별한 케이스 처리
		}
		else if (b == 4) {
			while (a--) {
				minNum = minNum + "8";
			}
			minNum = "20" + minNum; // 나머지가 4개일 때
		}
		else if (b == 5) {
			while (a--) {
				minNum = minNum + "8";
			}
			minNum = "28" + minNum; // 나머지가 5개일 때
		}
		else if (b == 6) {
			while (a--) {
				minNum = minNum + "8";
			}
			minNum = "68" + minNum; // 나머지가 6개일 때
		}
	}

	return minNum;
}

string MaxNum(int x){
	if (x == 2) return "1";
	else if (x == 3) return "7";

	int a = x / 2;

	string maxNum = "";
	if (x % 2 == 0) {
		while (a--){
			maxNum = maxNum + "1";
		}
	}
	else { // x % 2 == 1
		a--;
		while (a--) {
			maxNum = maxNum + "1";
		}
		maxNum = "7" + maxNum;
	}

	return maxNum;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> t;
	while (t--)
	{
		cin >> n;
		cout << MinNum(n) << " " << MaxNum(n) << "\n";
	}

	return 0;
}

 

 

---

 

다른 방식의 풀이:  동적계획법 (Dynamic Programming, DP)

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 성냥개비를 사용하여 만들 수 있는 숫자들의 배열
// index: 성냥개비 수, value: 해당 성냥개비 수로 만들 수 있는 최소 숫자
vector<string> dp(101, "0");

void init() // 성냥개비를 사용하여 만들 수 있는 숫자들 초기화
{
    // 각 숫자를 만드는 데 필요한 성냥개비의 최소 개수
    dp[2] = "1"; // 1
    dp[3] = "7"; // 7
    dp[4] = "4"; // 4
    dp[5] = "2"; // 2
    dp[6] = "6"; // 0 또는 6, 하지만 6을 사용하는 것이 더 낫다.
    dp[7] = "8"; // 8
    dp[8] = "10"; // 10이 최소
    
    // 9개 이상의 성냥개비를 사용하는 경우, 7개 또는 2개 성냥개비를 사용하는 숫자의 조합으로 해결
}

void findMinNum() // 주어진 성냥개비의 개수로 만들 수 있는 가장 작은 숫자를 찾는 함수
{
    for(int i = 9; i <= 100; ++i)
    {
        for(int j = 2; j <= 7; ++j) {
            string nextNum = dp[i-j] + (j == 6 ? "0" : dp[j]);
            if(dp[i] == "0" || dp[i] > nextNum) {
                dp[i] = nextNum;
            }
        }
    }
}

string MinNum(int n) {
    return dp[n];
}

string MaxNum(int n) 
{
    if(n % 2 == 1)
        return "7" + string(n / 2 - 1, '1');
    else
        return string(n / 2, '1');
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t, n;
    cin >> t;

    init();
    findMinNum();

    while(t--) {
        cin >> n;
        cout << MinNum(n) << " " << MaxNum(n) << "\n";
    }

    return 0;
}

 

 

주어진 성냥개비의 개수를 사용하여 만들 수 있는 가장 작은 숫자를 효율적으로 찾는 데 초점을 맞춥니다.

 

init 함수에서 성냥개비 2개부터 8개까지 만들 수 있는 최소 숫자들을 초기화한 후, findMinNum 함수에서 9개 이상의 성냥개비를 사용할 때 만들 수 있는 최소 숫자를 찾는다. 

 

가장 큰 숫자를 찾는 방법은 주어진 성냥개비로 가능한 한 많이 '1'을 만드는 것이다(홀수 개일 경우 첫 번째 숫자를 '7'(3개의 성냥개비 필요)로 만들어 나머지를 '1'로 채운다).

---

 

 

다른 방식의 풀이:  동적계획법 (Dynamic Programming, DP)

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 성냥개비로 만들 수 있는 숫자별 필요한 성냥개비 수 (0은 제외)
// 0은 사용되지 않지만, 인덱스를 맞추기 위해 포함
int matchsticks[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

string MinNum(int n) 
{
    if(n == 2) return "1"; // 예외 처리: 2개로 만들 수 있는 최소 숫자는 1
    
    // dp[i]는 i개의 성냥개비로 만들 수 있는 최소 숫자다.
    // INT_MAX로 초기화하여, 아직 계산되지 않았거나 불가능한 경우를 파악한다.
    vector<int> dp(n+1, INT_MAX); // dp[i]: i개의 성냥개비로 만들 수 있는 최소 숫자
    dp[0] = 0; 					  // 0개의 성냥개비는 0을 의미
    
    for(int i = 0; i <= n; ++i) { // 모든 성냥개비 수에 대해, 가능한 모든 숫자를 만든다.
        for(int num = 1; num < 10; ++num) { // 0은 성냥개비 6개가 필요하므로 여기서는 고려하지 않는다.
            if(i - matchsticks[num] >= 0) { // 현재 성냥개비 수에서 num을 만들 수 있다면,
                dp[i] = min(dp[i], dp[i - matchsticks[num]] + 1); // 현재의 최소값과 비교하여 더 작은 값을 선택.          }
        }
    }

    string result = "";
    for(int i = n; i > 0; ) {  // dp를 사용하여 만들 수 있는 최소 숫자를 거꾸로 추적
        for(int num = 1; num < 10; ++num) {
            if(i - matchsticks[num] >= 0 && dp[i] == dp[i - matchsticks[num]] + 1) { // 만약 num 숫자를 만드는 것이 현재 최소값을 만드는데 기여했다면,
                result += to_string(num); // 결과 문자열에 해당 숫자를 추가
                i -= matchsticks[num];    // 사용된 성냥개비 수만큼 빼준다.
                break; // 다음 숫자로 넘어감.
            }
        }
    }
    
    return result;
}

string MaxNum(int n) // 주어진 성냥개비의 개수로 만들 수 있는 가장 큰 숫자를 반환하는 함수
{
    string result = "";
    if(n % 2 == 1) { // 홀수인 경우
        result += "7"; // 7은 3개의 성냥개비가 필요하며, 가장 큰 한 자리 숫자
        n -= 3;
    }
    
    while(n > 0) {
        result += "1"; // 1은 2개의 성냥개비가 필요하며, 나머지를 모두 1로 채움
        n -= 2;
    }
    
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        cout << MinNum(n) << " " << MaxNum(n) << "\n";
    }

    return 0;
}

 

 

---