[Gold II] 성냥개비 - 3687
성능 요약
메모리: 13788 KB, 시간: 80 ms
분류
다이나믹 프로그래밍, 그리디 알고리즘
제출 일자
2024년 6월 7일 14:09:27
문제 설명
성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.
성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)
출력
각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다.
접근 방법
1. 문자열로 접근하여 숫자를 이어붙히는데 편리하게 사용한다.
2. dp[i] = dp[k] + dp[i - k] (k = 2 ~ (i- 2)까지) 점화식을 이용한다.
3. 7개까지는 직접 값을 넣어준 후 점화식을 이용해서 계산한다.
풀이 코드
import java.io.*;
/**
* 문제: BOJ_3687_성냥개비
* 메모리: 13788KB
* 시간: 80ms
* 접근 방법
* 1. 문자열로 접근하여 숫자를 이어붙히는데 편리하게 사용한다.
* 2. dp[i] = dp[k] + dp[i - k] (k = 2 ~ (i- 2)까지) 점화식을 이용한다.
* 3. 7개까지는 직접 값을 넣어준 후 점화식을 이용해서 계산한다.
*/
public class Main {
static String[] max, min;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
max = new String[101];
min = new String[101];
init();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
int idx = Integer.parseInt(br.readLine());
// 6이라면 최소값은 6으로 계산
if(idx == 6){
sb.append("6 ").append(getMax(idx));
}else{
sb.append(getMin(idx)).append(" ").append(getMax(idx));
}
sb.append("\n");
}
System.out.println(sb);
}
private static String getMin(int idx) {
if (min[idx] != null) {
return min[idx];
}
for (int i = 2; i <= idx - 2; i++) {
String front = min[i];
// 6이 앞자리면 0이 아닌 6을 넣어준다.
if(i == 6) front = "6";
if (front == null) {
getMin(i);
}
// null이면 새롭게 받아온다
if (min[idx - i] == null) {
getMin(idx - i);
}
String value = front + min[idx - i];
if (min[idx] == null) {
min[idx] = value;
} else if (compare(min[idx], value).equals(min[idx])) {
min[idx] = value;
}
}
return min[idx];
}
private static String getMax(int idx) {
if (max[idx] != null) {
return max[idx];
}
max[idx] = "0";
for (int i = 2; i <= idx - 2; i++) {
if (max[i] == null) {
getMax(i);
}
if (max[idx - i] == null) {
getMax(idx - i);
}
String value = max[i] + max[idx - i];
max[idx] = compare(max[idx], value);
}
return max[idx];
}
private static String compare(String a, String b) {
if (a.equals(b)) {
return a;
} else if (a.length() > b.length()) {
return a;
} else if (a.length() < b.length()) {
return b;
} else {
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
if (a.charAt(i) > b.charAt(i)) {
return a;
} else {
return b;
}
}
}
}
return a;
}
private static void init() {
max[2] = min[2] = "1";
max[3] = min[3] = "7";
max[4] = "11"; min[4] = "4";
max[5] = "71"; min[5] = "2";
max[6] = "111"; min[6] = "0";
max[7] = "711"; min[7] = "8";
min[8] = "10"; min[9] = "18";
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 1113번 : 수영장 만들기 Gold1(골드1) - JAVA[자바] (0) | 2024.06.11 |
---|---|
[백준] 5549번 : 행성 탐사 Gold5(골드5) - JAVA[자바] (2) | 2024.06.08 |
[백준] 14676번 : 영우는 사기꾼? Gold3(골드3) - JAVA[자바] (1) | 2024.06.06 |
[백준] 1484번 : 다이어트 Gold5(골드5) - JAVA[자바] (1) | 2024.06.05 |
[백준] 1700번 : 멀티탭 스케줄링 Gold1(골드1) - JAVA[자바] (1) | 2024.06.04 |