[백준 / 골드3] 3165 5 (Java)

문제 보기

사용한 것

• 조건을 만족하는 최소 숫자를 구하기 위한 백트래킹

풀이 방법

• 일의 자리수(idx)부터 증가시키면서 백트래킹한다.
• 다음의 우선순위로 '5'의 개수가 충족되거나 n의 길이까지 백트래킹
  • 현재 자릿수가 5보다 작으면 5로 만들고 재귀
  • 현재 자릿수가 5보다 크면 현재 자릿수에서 반올림, flag true
  • 현재 자릿수가 5면 다음 다음 자릿수로 호출
• 탐색할때마다 count()로 5의 개수를 체크한다.
• 체크 후 flag인 경우 이전 자릿수를 5로 설정한다.
• "48 1"과 같은 반례 때문에 반올림 후 체크하고 이전 자리수를 5로 설정하는 것이다.

코드

public class Main {

    private static final char FIVE = '5';
    private static StringBuilder n;
    private static int k;

    public static void main(String[] args) throws IOException {
        init();
        backtrack(0, false);
        addRemaining();
        System.out.println(new StringBuilder(n).reverse());
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = new StringBuilder(String.valueOf(Long.parseLong(st.nextToken()) + 1))
            .reverse();
        k = Integer.parseInt(st.nextToken());
        br.close();
    }

    private static void backtrack(int idx, boolean flag) {
        if (idx >= n.length() || count() >= k) {
            return;
        }

        if (flag) {
            n.setCharAt(idx - 1, FIVE);
        }

        if (count() >= k) {
            return;
        }

        if (n.charAt(idx) < FIVE) {
            n.setCharAt(idx, FIVE);
            backtrack(idx + 1, false);
        } else if (n.charAt(idx) > FIVE) {
            n.setCharAt(idx, '0');
            roundUp(idx);
            backtrack(idx + 1, true);
        } else {
            backtrack(idx + 1, false);
        }
    }

    private static int count() {
        int ct = 0;
        for (int i = 0; i < n.length(); i++) {
            if (n.charAt(i) == FIVE) {
                ct++;
            }
        }
        return ct;
    }

    private static void roundUp(int idx) {
        long add = 10;
        for (int i = 0; i < idx; i++) {
            add *= 10;
        }
        n = new StringBuilder(String.valueOf(Long.parseLong(n.reverse().toString()) + add))
            .reverse();
    }

    private static void addRemaining() {
        int ct = count();
        for (int i = ct; i < k; i++) {
            n.append(FIVE);
        }
    }
}