백준 3687 성냥개비

문제링크 : https://www.acmicpc.net/problem/3687

아이디어

• 가장 큰수일떄 : 자리수가 길어야하고, 같은자리수라면 큰수가 먼저
  • 성냥개비 가장 작게사용 : 1(2), 7(3)
  • 그리디 방법 사용 > 처음에 홀수이면 7, 짝수이면 2 붙임
• 가장 작은수 : 자리수가 작아야하고, 같은자리수라면 작은수 먼저
  • 가장 작은 자리수 구하는 방법
    • 주어진 성냥개비로 작은 자리수부터 가능한지 확인
    • 앞에 어떤자리수 들어가면 7XXX
    • 뒤에 남은 성냥개비수로 가능한지 확인하면됨
    • 이전값을 재활용할수 있음 > DP 사용
    • DP[K][N] : 성냥개비 N개로 K자리수를 만들수 있는지
  • 앞에 작은수부터 넣어서 남은 성냥개비로 가능한지 확인
    • 이때 DP로 남은 성냥개비로 숫자 만들수 있는지 확인

시간복잡도 계산

• 큰수 확인
  • 테스트케이스 : T
  • 성냥개비 N번 반복 : N
  • 합 : O(NT)
• 작은수 확인
  • 테스트케이스 : T
  • DP값 계산
    • N개 성냥개비로
    • K자리수가능한지 확인(K최대 50, 성냥개비 최대 100개일떄 1로만 만드는경우)
    • O(NK)
  • 작은수부터 넣기
    • N개 성냥개비
    • 모든 숫자 확인 : 10
    • O(10N)
• 총합 : O(NT + T(NK+10N)) = O(TN^2) = 100^3 = 1e6 > 가능

자료구조

• 총합 : O(NT + T(NK+10N)) = O(TN^2) = 100^3 = 1e6 > 가능

코드(C++)

#include <iostream>
#include <string>
 
using namespace std;
 
int nums[10] = {6,2,5,5,4,5,6,3,7,5};
bool dp[60][110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // DP 먼저 구하기
    fill(&dp[0][0], &dp[59][110], 0);
    dp[0][0] = 1;
    for(int j=1; j<=50; j++) {
        for(int i=0; i<=100; i++) {
            for(int k=0; k<10; k++) {
                // 가지고 있는 성냥개비가 부족할떄
                if(i-nums[k]<0) continue;
                if(dp[j-1][i-nums[k]]) dp[j][i] = 1;
            }
        }
    }
    
    int T; cin >> T;
    while(T--) {
        
        string maxv;
        string minv;
        int N; cin >> N;
        
        // 최대값 먼저 구하기
        int maxN = N;
        while(maxN >0) {
            if(maxN % 2 == 1) {
                maxv += "7";
                maxN -= 3;
            } else {
                maxv += "1";
                maxN -= 2;
            }
        }
        
        
        // 최소값 구하기
        // 최소자리부터 구하자
        int len;
        for(int k=1; k<=50; k++) {
            if(dp[k][N]) {
                len = k;
                break;
            }
        }
        // 첫자리는 0이 불가하므로 1부터 계산
        for(int i=1; i<=9; i++) {
            if(N-nums[i] >=0) {
                if(dp[len-1][N-nums[i]]) {
                    minv += '0'+i;
                    N -= nums[i];
                    len--;
                    break;
                }
            }
        }
        // 다음 자리
        while(N>0) {
            for(int i=0; i<=9; i++) {
                if(N-nums[i] >=0) {
                    if(dp[len-1][N-nums[i]]) {
                        minv += '0'+i;
                        N -= nums[i];
                        len--;
                        break;
                    }
                }
            }
        }
        cout << minv << ' ' << maxv << '\n';
        
        
    }
    
    return 0;
}
 

문제유형

• DP - 최소값
  • 주어진 개수로 최소값을 만들어야할때 조건
  • 2가지 조건 만족해야함 : 자리수 최저, 앞의 숫자일수록 작은수
  • 주어진 개수로 가능한 자리수를 DP로 만들어준뒤, 낮은수 부터 추가하면서 남은 개수로 남은 자리수를 만들수 있는지 확인하면서 추가