SWEA D4 7206 숫자게임

SWEA D4 7206 숫자게임

 

 

문제링크

http://www.swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWlGyBQqaEgDFASG&categoryId=AWlGyBQqaEgDFASG&categoryType=CODE&&&

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/svZDw79kPF0

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.d5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;

public class SWEA_D4_7206_숫자게임 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();

    static int T, N;

    // 숫자들이 쪼개진 회수
    static int[] memo;

    static boolean[] status;

    public static void main(String[] args) throws IOException {
        // 어차피 동일한 로직으로 숫자를 뽑아 놓을 거니까 다 구해놓자.
        init();

        input = new BufferedReader(new StringReader(src));
        T = Integer.parseInt(input.readLine().trim());
        for (int t = 1; t <= T; t++) {

            N = Integer.parseInt(input.readLine().trim());

            output.append("#").append(t).append(" ").append(memo[N]).append("\n");
        }
        System.out.println(output);
    }

    static void init() {
        // 숫자는 최대 99999 까지 이다.
        memo = new int[99999 + 1];
        Arrays.fill(memo, -1);
        status = new boolean[memo.length - 1];
        for (int i = 0; i < memo.length; i++) {
            if (i < 10) {
                memo[i] = 0;
            } else {
                int cnt = calculate(i);
                memo[i] = cnt;
            }
        }
    }

    static int calculate(int value) {
        // value를 쪼개서 만들 수 있는 부분집합들로 가지수를 세보자.
        String str = value + "";
        int len = str.length();
        // str의 길이보다 1개 작은 크기의 요소들로 이뤄진 부분집합이 필요. 공집합은 필요 없다.
        for (int i = 1; i < 1 << len - 1; i++) {
            for (int j = 0; j < len; j++) {
                // 해당 위치에서 쪼개지는지 여부 설정
                status[j] = (i & (1 << j)) > 0;
            }
            // 현재의 str로 만들 수 있는 어떤 값
            int newNum = makeNewNum(str, len);
            // memo의 값은 기존의 newNum의 값 + 1 과 누군가 만들어 놓은 기존 값 중 최대 값
            memo[value] = Math.max(memo[value], memo[newNum] + 1);
        }
        return memo[value];
    }

    static int makeNewNum(String val, int len) {
        int newNum = 1;
        // 첫 번째 숫자를 기준으로 삼자
        int temp = val.charAt(0) - '0';
        for (int i = 0; i < val.length() - 1; i++) {
            if (status[i]) {// 잘라야 하는 곳이라면...
                newNum *= temp;
                temp = val.charAt(i + 1) - '0';
            } else {
                temp = temp * 10 + val.charAt(i + 1) - '0';
            }
        }
        // 마지막으로 남은 temp와 newNum을 곱해서 반환
        return newNum * temp;
    }

    private static String src = "5\n" +
                                "6\n" +
                                "79\n" +
                                "123\n" +
                                "423\n" +
                                "1089";
}