[BOJ/C++] 성냥 개비(3687번)

1. 개요

https://acmicpc.net/problem/3687

1-1. 설명

 

성냥 개비를 이용하여 만든 숫자들

성냥개비로 위와 같은 숫자를 만드려고한다. 성냥개비의 개수가 주어졌을 때, 성냥 개비를 모두 사용해 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성한다.

1-2. 제한 사항

- 첫 줄에 테스트 케이스 개수가 주어지며, 최대 100개

- 각 테스트 케이스는 한줄로 이루어져 있고, 성냥개비 개수 n이 주어짐

- n 은 2 이상 100 이하의 자연수

- 각 테스트 케이스에 대해 입력으로 주어진 성냥 개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 출력

---

2. 구현

2-1. 풀이

큰 수는 자릿수가 많을수록 커지므로, 1과 7을 이용하여 만든다. 1은 2개, 7은 3개로 다른 숫자들은 4개 이상이므로 1과 7을 이용하면 된다. 

 - n이 짝수인 경우 : 1로만 배치

 - n이 홀수인 경우 : 1로 배치 후 맨 앞 자리수를 7로 변경

 

작은 수는 다이나믹 프로그래밍을 통해 구해야 한다. 성냥개비의 개수 2~100개 까지를 dp 배열에 저장하고 100까지 반복문을 통해 작은 수를 계산한다. 성냥개비 개수인 2~8개까지는 각각 숫자에 맞게끔 초기화를 시켜준다.

long long dp[MAX_COUNT] = { 0, 0, 1, 7, 4, 2, 6, 8, 10 };

 

여기서 한자리수는 0이 최솟값이 되면 안되므로, 성냥개비가 6개일때는 6이 들어가게 된다. 이후에 dp 배열을 통해 최솟값을 계산할 배열을 선언 및 초기화 한다

int fireStickArray[6] = {1, 7, 4, 2, 0, 8};

 

반복문은 9로 시작하여, 각 dp[i]에서 2~7개의 성냥개비 개수를 통해 최솟값을 구해야 한다. 

long long cur = (dp[i - j] * 10) + fireStickArray[j - 2];
j == 2 ? (dp[i] = cur) : (dp[i] = min(dp[i], cur));
// example > 9개일 때
// dp[9-2] * 10 + fireStickArray[0] (성냥 개수 : 7 + 2)
// dp[9-3] * 10 + fireStickArray[1] (성냥 개수 : 6 + 3)
// ...
// dp[9-7] * 10 + fireStickArray[7] (성냥개수 : 2 + 7)
// (* 10)은 자릿수 추가를 위함
// 계산 후 2~7개 중에서 최솟값을 dp[9]에 저장

 

최솟값을 n이 100개인 경우까지 구해서 테스트 케이스를 받을 때마다 dp[n]을 출력해주면 된다. 

2-2. 코드

#include <iostream>
#include <algorithm>

#define MAX_COUNT 101

using namespace std;

long long dp[MAX_COUNT] = { 0, 0, 1, 7, 4, 2, 6, 8, 10 };
int fireStickArray[6] = {1, 7, 4, 2, 0, 8};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int tc, n;
    string max;
    cin >> tc;

    // dynamic programming
    for (int i = 9; i < MAX_COUNT; i++) {
        for (int j = 2; j <= 7; j++) {
            long long cur = (dp[i - j] * 10) + fireStickArray[j - 2];
            j == 2 ? (dp[i] = cur) : (dp[i] = min(dp[i], cur));
            // 성냥개비 2 ~ 7 범위에서 최솟값 계산
        }
    }

    while (tc--)
    {
        cin >> n;

        max = "";

        // greedy algorithm
        for (int i = 0; i < n / 2; i++) max += "1";

        if (n % 2 == 1)
            max[0] = '7';
        // 최댓값 : 7,1로만 이루어짐 -> 자릿수가 많을수록 큰 숫자이므로

        cout << dp[n] << ' ' << max << "\n";
    }
}

---

참고 문서

https://dingdingmin-back-end-developer.tistory.com/entry/%EB%B0%B1%EC%A4%80-3687%EC%9E%90%EB%B0%94-java-%EC%84%B1%EB%83%A5%EA%B0%9C%EB%B9%84

백준 3687[자바] java 성냥개비