문제 링크
문제
티어: 골드 2
알고리즘: 그리디
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)
출력
각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다.
풀이
성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 출력해야 한다.
가장 큰 수를 구하려면 수 길이를 최대한 늘려야 한다.
그러기 위해서는 성냥개비 2개를 사용하는 숫자 1를 최대한 사용하는 것이다.
왜냐하면 성냥개비 4개 이상부터는 자릿수를 최대 하나 이상 늘릴 수 있기 때문이다.
하지만 성냥개비 수가 3인 경우는 숫자 1대신 숫자 7(숫자 7은 성냥개비 3개 사용됨)을 사용하는 경우가 더 큰 수가 된다.
그래서 성냥개비 수를 2로 나눴을 때 나머지가 0이 아닌 경우 첫 번째를 숫자 7로 나머지는 숫자 1로 채우면 그 값이 가장 큰 값이 된다.
가장 작은 수를 구하는 것은 더 까다롭다. 가장 작은 수는 반대로 수 길이를 최대한 줄여야 한다.
그러면 수 길이를 최대한 줄이려면 성냥개비를 가장 많이 사용하는 숫자 8을 이용하면 될까??
결론부터 말하면 맞지만, 숫자 2랑은 좀 다른게 나머지가 7 ~ 13이기 때문에 증명하는게 조금 까다로웠다.
증명 과정을 간략하게 설명하자면,
성냥개비 7개 다음으로 많이 사용하는 숫자는 6이며, 성냥개비 6개를 사용한다.
숫자 8을 두 번 사용한다면 숫자 6도 당연히 두 번 이상 사용된다. 이때 성냥개비의 차이는 2 * (7 - 6) = 2이기 때문에 그러니까 2개 더 사용했기 때문에 자릿수를 하나 더 줄일 수 있다.
그래서 성냥개비의 개수가 14이상인 경우는 무조건 숫자 8을 최대한 사용하는게 최선이다.
그러면 성냥개비 13까지만 가장 작은 수를 직접 구해서 활용하면 문제는 쉬워진다.
성냥개비 개수를 7로 나누고, 나머지가 0이 아닌경우는 7 ~ 13이기 때문에 앞에서 구해놓은 가장 작은 수를 맨 앞에 붙이고, 나머지를 숫자 8로 채우면 된다.
여기서 주의할 점은 성냥개비 개수가 10개인 경우 가장 작은 수는 22고,
성냥개비 개수가 12인 경우는 가장 작은 수는 28이지만, 이 수가 첫 번째 자리가 아니라면 00이 들어가는게 최선이다. (성냥개비 수가 6개인 경우는 6과 0이 있다.)
그래서 이를 따로 처리해줘야 하는데, 완성된 가장 작은 수가 228888...인 경우에 28을 00으로 바꿔줘야된다. (28은 나머지 성냥개비 수가 10인 경우 22가 가장 앞에 붙게되고, 8이 추가적으로 붙는 경우에만 발생한다.)
이 풀이는 그리디 풀이이며, 시간 복잡도는 O(n)보다 작다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int T;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
int[] dp = new int[14];
dp[2] = 1;
dp[3] = 7;
dp[4] = 4;
dp[5] = 2;
dp[6] = 6;
dp[7] = 8;
dp[8] = 10;
dp[9] = 18;
dp[10] = 22;
dp[11] = 20;
dp[12] = 28;
dp[13] = 68;
for (int i = 0; i < T; i++) {
int n = Integer.parseInt(br.readLine());
if (n < 7) {
sb.append(dp[n]);
} else {
int c = n / 7;
if(n % 7 != 0) {
c -= 1;
if(n % 7 == 3 && c > 0) {
c -= 1;
sb.append(200);
} else {
sb.append(dp[7 + n % 7]);
}
}
for(int j=0; j<c; j++) {
sb.append(8);
}
}
sb.append(" ");
for(int j=0; j<n/2; j++) {
if(j == 0 && n % 2 == 1) {
sb.append(7);
continue;
}
sb.append(1);
}
sb.append("\n");
}
System.out.println(sb.toString().trim());
}
}