
https://www.acmicpc.net/problem/3687
문제분석
성냥개비 갯수가 주어지면, 해당 성냥개비로 만들 수 있는 숫자 최대값/최소값을 구해야한다. Dynamic Programming을 활용해 문제를 해결해야 한다. 이번 문제에서는 index를 '성냥 갯수', 저장하는 값을 'index 성냥갯수로 만들 수 있는 최소값' 이다.
최대값은? 잘 보면, 최대값은 '자릿수'가 많은게 깡패다. 또한 모든 성냥개비를 다 써야하는 조건때문에 최대값에서 쓰이는 숫자는 7(성냥3개)과 1(성냥2개)밖에 없다. 따라서 홀수일 때 7을 1개만 쓰고, 짝수일 때 1만 써서 수를 나타내면 된다. Greedy로 해결된다.
성냥개비 갯수가 n개 주어져서 어떻게 배열 크기를 정해야 하나 할 수 있지만, 문제 조건을 읽어보면 1<n<101이다. 101번의 연산은 시간적으로 부담되는 수치가 아니므로 미리 계산해두고, 필요한 값을 index를 통해 가져오는 방식을 채택했다.
점화식은 다음과 같다
minDp[i] = Math.min(minDp[i], minDp[i-숫자 j를 위한 성냥 갯수]*10+숫자 j);
숫자j를 1의 자리에 추가하는 방식으로 101까지 연산을 해나가면 된다.
코드
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static int[] nums = {6,2,5,5,4,5,6,3,7,6}; // 인덱스가 숫자, 값이 성냥개비 갯수
public static void main(String[]args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
long[] minDp = new long[101];
Arrays.fill(minDp, Long.MAX_VALUE);
minDp[2]=1;
minDp[3]=7;
minDp[4]=4;
minDp[5]=2;
minDp[6]=6;
minDp[7]=8;
minDp[8]=10;
for(int i = 9; i < 101; i++){
for(int j = 0; j<10; j++){
if(i>nums[j]){
minDp[i] = Math.min(minDp[i], minDp[i-nums[j]]*10+j);
}
}
}
for(int i = 0; i < N; i++){
int count = Integer.parseInt(br.readLine());// 성냥개비 갯수(전부 사용해야 함)
long minResult = minDp[count];
String maxResult = "";
int high = count / 2; // 몫.
int low = count % 2; //홀수면 1, 짝수면 0
for(int j = 0; j<high-1;j++){
maxResult+="1";
}
maxResult = (low==1?"7":"1") + maxResult;
bw.write(minResult+" "+maxResult);
bw.newLine();
}
bw.flush();
bw.close();
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 1328 고층 빌딩 (0) | 2025.09.01 |
|---|---|
| [JAVA] 백준 2618 경찰차 (0) | 2025.08.20 |
| [JAVA] 백준 1106 호텔 (2) | 2025.08.16 |
| [JAVA] 백준 12865 평범한 배낭(with knapsack) (3) | 2025.08.15 |
| [JAVA] 백준 1202 보석도둑 (3) | 2025.08.13 |