백준 1443 망가진 계산기 - JAVA

1443 문제 링크

---

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    private static int D, P;
    private static int max = -1;
    private static int limit = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        D = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        limit = (int) Math.pow(10, D);
       dfs(1, 0, 2);
        bw.write(String.valueOf(max));
        bw.flush();
    }
    private static void dfs(int num, int depth, int start) {
        if (depth == P) {
            max = Math.max(max, num);
            return;
        }
        for (int i = start; i <= 9; i++) {
            if (num * i < limit) dfs(num * i, depth + 1, i);
        }
    }
}

 

알고리즘 설명

---

꼭 티어 때문에 어렵게 생각하게 되는 문제들이 있는 것 같습니다.

뭐... 문제를 푸는 방식은 크게 어렵지 않습니다. 다만, 저도 한 가지를 생각을 못하고 조금 헤맸네요.

 

이 문제는 정해진 자리수를 초과하지 않으면서 가장 큰 수를 만드는 것이 핵심입니다. 곱할 수는 2부터 9까지의 수인데, 단순히 순서를 바꾼 경우에도 결과가 같을 수 있습니다. 예를 들어

1. 1 * 2 * 9...
2. 1 * 9 * 2...

가 순서만 다르고 결과 값은 동일하기 때문에 순서를 고려하지 않고 중복 계산을 하지 않는 방법이 필요합니다. 따라서, 현재 선택된 수 보다 이상의 수만 곱해지도록 제한하면 순서만 다르고 결과 값은 같은 중복 계산을 방지할 수 있습니다.

 

코드 해석

---

P의 값이 최대 30까지 이지만 D의 값이 8까지이므로, 자료형도 int 범위내에서 충분한 것 같습니다.

먼저 limit 변수에 10^D 값을 저장하고, 2부터 9까지 반복문을 돌며 현재 숫자에 곱했을 때 limit을 넘지 않으면 백트래킹을 수행합니다.

 

이때, 백트래킹 내에서 다음 단계의 반복문 시작 값을 현재 곱한 숫자부터로 설정하여, 이전 단계에서 곱해진 수보다 작은 수로 중복 계산하지 않도록 합니다.