1528번: 금민수의 합
금민수 = 4와 7로만 이루어진 수
숫자 N(N ≤ 1,000,000)을 금민수의 합으로 나타내라. 여러 방법이 존재한다면 수의 개수가 적은 것을 출력한다.
그러한 방법도 여러 개일 경우 사전 순으로 가장 앞서는 것을 출력.
표현할 수 없다면 -1
- 금민수의 합으로 나타내는 방법을 알아야 한다.
- 여러 방법이 존재하는지 확인하기 위해 저장을 해야 한다.
- 사전순으로 정렬은 문자열의 기본 정렬이다.
만약 N 보다 작은 금민수를 전부 찾아서 저장할 수 있을까? → 메모리상으로는 가능하다.
그런데 전부 찾아서 저장하더라도 해당 조합을 재귀로 찾기에는 너무 많다.
예를 들어 100을 생각해 보자. 100보다 작은 금민수는 4, 7, 44, 47, 74, 77이 존재한다.
100을 만들 수 있는가? = 23 or 26 or 56 or 93 or 96을 금민수의 조합으로 만들 수 있느냐
23 → 4, 7 → 19, 16을 만들 수 있는가
16 → 4, 7 → 12, 9를 만들 수 있는가
12 → 4, 7 → 8, 5를 만들 수 있는가
8 → 4, 7 → 4, 1을 만들 수 있는가
4 → 4 → 성공
DP다. 만들 수 없음을 -1을 두고 만들 수 있는 것은 최소 개수를 저장한다.
- 먼저 N보다 작은 금민수를 만든다.
- bottom - up으로 0부터 dp를 채운다.
- 최소개수가 더 적다면 갱신이 된다면 구성되는 숫자를 덮어 씌운다.
- 최소개수가 동일하다면 구성 숫자를 사전순으로 비교한 후 덮어 씌운다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static FastReader scan = new FastReader();
static int N;
static final String[] nums = {"4", "7"};
static List<Integer> fourSeven = new ArrayList<>();
static final int INF = Integer.MAX_VALUE;
static void input() {
N = scan.nextInt();
}
static void getFourSeven(StringBuilder curr) {
if (curr.length() > 0 && Integer.parseInt(curr.toString()) > N) {
return;
}
if (curr.length() > 0 ) {
fourSeven.add(Integer.parseInt(curr.toString()));
}
for (String num : nums) {
curr.append(num);
getFourSeven(curr);
curr.deleteCharAt(curr.length() - 1);
}
}
public static void main(String[] args) throws IOException {
input();
getFourSeven(new StringBuilder());
Collections.sort(fourSeven);
int[] dp = new int[N + 1];
Arrays.fill(dp, INF);
List<Integer>[] sequences = new ArrayList[N + 1];
dp[0] = 0;
sequences[0] = new ArrayList<>();
for (int i = 0; i <= N; i++) {
if (dp[i] == INF) continue;
for (int num : fourSeven) {
int next = i + num;
if (next > N) continue;
if (dp[i] + 1 < dp[next]) {
dp[next] = dp[i] + 1;
sequences[next] = new ArrayList<>(sequences[i]);
sequences[next].add(num);
} else if (dp[i] + 1 == dp[next]) {
List<Integer> newSeq = new ArrayList<>(sequences[i]);
newSeq.add(num);
if (isFirst(newSeq, sequences[next])) {
sequences[next] = newSeq;
}
}
}
}
if (dp[N] == INF) {
System.out.println(-1);
} else {
StringBuilder sb = new StringBuilder();
for (int num : sequences[N]) {
sb.append(num).append(" ");
}
System.out.println(sb.toString().trim());
}
}
static boolean isFirst(List<Integer> newSeq, List<Integer> seq) {
for (int i = 0; i < Math.min(newSeq.size(), seq.size()); i++) {
if (!newSeq.get(i).equals(seq.get(i))) {
return newSeq.get(i) < seq.get(i);
}
}
return newSeq.size() < seq.size();
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
메모리 초과가 발생헀다.
dp 배열 크기는 4MB로 문제없지만 sequences의 실제 데이터에서 문제가 발생하는 것 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static FastReader scan = new FastReader();
static int N;
static final String[] nums = {"4", "7"};
static List<Integer> fourSeven = new ArrayList<>();
static final int INF = Integer.MAX_VALUE;
static void input() {
N = scan.nextInt();
}
static void getFourSeven(StringBuilder curr) {
if (curr.length() > 0 && Integer.parseInt(curr.toString()) > N) {
return;
}
if (curr.length() > 0) {
fourSeven.add(Integer.parseInt(curr.toString()));
}
for (String num : nums) {
curr.append(num);
getFourSeven(curr);
curr.deleteCharAt(curr.length() - 1);
}
}
public static void main(String[] args) throws IOException {
input();
getFourSeven(new StringBuilder());
Collections.sort(fourSeven);
int[] dp = new int[N + 1];
int[] prev = new int[N + 1];
int[] used = new int[N + 1];
Arrays.fill(dp, INF);
Arrays.fill(prev, -1);
dp[0] = 0;
for (int i = 0; i <= N; i++) {
if (dp[i] == INF) continue;
for (int num : fourSeven) {
int next = i + num;
if (next > N) continue;
if (dp[i] + 1 < dp[next]) {
dp[next] = dp[i] + 1;
prev[next] = i;
used[next] = num;
} else if (dp[i] + 1 == dp[next]) {
List<Integer> currentPath = getPath(i, prev, used);
currentPath.add(num);
List<Integer> existingPath = getPath(next, prev, used);
if (isFirst(currentPath, existingPath)) {
prev[next] = i;
used[next] = num;
}
}
}
}
if (dp[N] == INF) {
System.out.println(-1);
} else {
List<Integer> answer = getPath(N, prev, used);
StringBuilder sb = new StringBuilder();
for (int num : answer) {
sb.append(num).append(" ");
}
System.out.println(sb.toString().trim());
}
}
// 경로 복원 함수
static List<Integer> getPath(int n, int[] prev, int[] used) {
List<Integer> path = new ArrayList<>();
while (n > 0) {
path.add(used[n]);
n = prev[n];
}
Collections.sort(path);
return path;
}
static boolean isFirst(List<Integer> newSeq, List<Integer> seq) {
for (int i = 0; i < Math.min(newSeq.size(), seq.size()); i++) {
if (!newSeq.get(i).equals(seq.get(i))) {
return newSeq.get(i) < seq.get(i);
}
}
return newSeq.size() < seq.size();
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
위치를 저장하는 배열을 사용하도록 변경했다. 하지만 역시 메모리 초과가 발생했다…
뭐가 원인인지 파악하지 못해 풀이를 dp에서 다른 방식으로 찾아보기로 하였다.
BFS방식을 사용하도록 하겠다.
BFS는 레벨별 탐색 즉 사용한 금민수의 개수별로 탐색이 진행되기 때문에 원하는 답에 최소 개수로 도달할 수 있다. 또한 사용하는 금민수를 사전순으로 정리해 두면 자연스럽게 사전순으로 빠른 것을 먼저 찾는다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static FastReader scan = new FastReader();
static int N;
static final String[] nums = {"4", "7"};
static List<Integer> fourSeven = new ArrayList<>();
static final int INF = Integer.MAX_VALUE;
static void input() {
N = scan.nextInt();
}
static void getFourSeven(StringBuilder curr) {
if (curr.length() > 0 && Integer.parseInt(curr.toString()) > N) {
return;
}
if (curr.length() > 0) {
fourSeven.add(Integer.parseInt(curr.toString()));
}
for (String num : nums) {
curr.append(num);
getFourSeven(curr);
curr.deleteCharAt(curr.length() - 1);
}
}
static class State {
int sum;
List<Integer> nums;
State(int sum, List<Integer> nums) {
this.sum = sum;
this.nums = nums;
}
}
public static void main(String[] args) throws IOException {
input();
getFourSeven(new StringBuilder());
Collections.sort(fourSeven);
Queue<State> queue = new LinkedList<>();
boolean[] visited = new boolean[N + 1];
queue.add(new State(0, new ArrayList<>()));
visited[0] = true;
while (!queue.isEmpty()) {
State curr = queue.poll();
if (curr.sum == N) {
StringBuilder sb = new StringBuilder();
for (int num : curr.nums) {
sb.append(num).append(" ");
}
System.out.println(sb.toString().trim());
return;
}
for (int num : fourSeven) {
int nextSum = curr.sum + num;
if (nextSum > N || visited[nextSum]) continue;
List<Integer> nextNums = new ArrayList<>(curr.nums);
nextNums.add(num);
queue.add(new State(nextSum, nextNums));
visited[nextSum] = true;
}
}
System.out.println(-1);
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
