[SWEA/Java] 7206. 숫자 게임

[SWEA/Java] 7206. 숫자 게임

SW Expert Academy

---

문제 해석

이 문제에서는 주어진 숫자를 일정 규칙에 따라 분할하고, 각 부분의 곱을 계산하여 다시 하나의 숫자를 생성한다. 이 과정을 반복할 때, 숫자를 분할하여 계산을 수행한 총 횟수를 최대화하는 것이 목표다. 예를 들어, 숫자 '123'은 '1 * 23 = 23' 또는 '12 * 3 = 36'으로 분할하여 계산할 수 있다. 만약 결과값이 10보다 크면 다시 분할할 수 있다.

풀이 과정

제출된 코드는 숫자를 여러 가지 방법으로 분할하고, 각 분할의 결과에 대해 최대 분할 횟수를 구하기 위해 동적 계획법(Dynamic Programming)을 사용한다.

 

1. dp 배열: 숫자 i를 입력받았을 때, 최대 분할 횟수를 저장한다.
2. setPermutation 함수: 주어진 숫자에 대해 가능한 모든 분할을 시도한다.
3. permutation 함수: 특정 분할 구성에 대해 숫자를 분할하고, 분할된 숫자들의 곱을 계산한다. 계산된 결과가 10 이상일 경우, 결과값을 다시 터치한다.
4. makeNum 함수: 분할된 인덱스에 따라 숫자를 분할하고 곱한다. 곱의 결과가 10 미만일 경우, 추가 분할은 불가능하며 해당 숫자의 최대 분할 횟수는 1로 갱신한다.

코드

package edu.ssafy.im.SWEA.D5.No7206;

import java.io.*;
import java.util.*;

public class Solution {
    private String num; // 입력받은 숫자를 문자열로 저장
    private ArrayList<Integer> numList; // 분할된 숫자를 저장하는 리스트
    private int ans; // 최대 분할 횟수를 저장하는 변수
    private int[] dp; // 각 숫자별 최대 분할 횟수를 저장하는 배열

    public static void main(String[] args) throws IOException {
        new Solution().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        for (int t = 1; t <= T; t++) {
            num = br.readLine(); // 숫자 입력
            ans = Integer.MIN_VALUE; // 최대값 계산을 위해 최소값으로 초기화
            sol(); // 솔루션 실행
            sb.append("#").append(t).append(" ").append(ans).append("\n"); // 결과 문자열 생성
        }
        bw.write(sb.toString()); // 결과 출력
        bw.flush();
        bw.close();
    }

    private void sol() {
        dp = new int[Integer.parseInt(num)+1]; // 숫자 크기만큼 dp 배열 초기화
        if (num.length() > 1) { // 숫자의 길이가 1보다 큰 경우에만 분할 가능
            setPermutation(num); // 분할 시도
            ans = dp[Integer.parseInt(num)]; // 최대 분할 횟수 저장
        } else {
            ans = 0; // 길이가 1인 경우 분할 횟수는 0
        }
    }

    private void setPermutation(String num) {
        for (int i = 1; i < num.length(); i++) {
            int[] sel = new int[i]; // 분할할 위치를 저장할 배열
            permutation(0, 0, num, sel); // 분할 위치 결정
        }
    }

    private void permutation(int k, int v, String num, int[] sel) {
        if(k == sel.length) {
            int res = makeNum(num, sel); // 분할된 숫자로부터 곱을 계산

            if(res != -1) { // 곱의 결과가 10 이상인 경우
                if (dp[res] == 0) { // 해당 숫자를 처음 방문하는 경우
                    setPermutation(String.valueOf(res)); // 재귀적으로 분할 시도
                }
                if (dp[res] + 1 > dp[Integer.parseInt(num)]) { // 현재 숫자의 최대 분할 횟수를 갱신
                    dp[Integer.parseInt(num)] = dp[res] + 1;
                }
            }
            return;
        }

        // 분할할 부분 선택
        for (int i = 0; i < num.length()-1; i++) {
            if((v & (1 << i)) == 0) {
                sel[k] = i+1;
                permutation(k+1, v |= 1 << i, num, sel);
            }
        }
    }

    private int makeNum(String num, int[] sel) {
        numList = new ArrayList<>();
        numList.add(Integer.parseInt(num.substring(0, sel[0])));
        if (sel.length > 1) {
            for (int i = 0; i < sel.length-1; i++) {
                numList.add(Integer.parseInt(num.substring(sel[i], sel[i+1])));
            }
        }
        numList.add(Integer.parseInt(num.substring(sel[sel.length-1], num.length())));

        int sum = 1;
        for (int n: numList) {
            sum *= n; // 분할된 숫자들의 곱을 계산
        }
        if (sum < 10) {
            dp[Integer.parseInt(num)] = 1; // 곱의 합이 10보다 작으면 분할 횟수는 1
            return -1;
        }
        return sum; // 분할 가능한 새로운 숫자 반환
    }
}

시간 복잡도 분석

코드의 시간 복잡도는 dp 배열과 숫자 분할 과정의 복잡성에 의해 결정된다. 분할 과정은 숫자의 길이에 따라 O(2N)가 될 수 있으며, 각 숫자마다 최대 N개의 분할 결과를 처리해야 한다.

느낀점

이 문제를 통해 복잡한 숫자 분할 및 동적 계획법을 사용하여 최적화 문제를 해결하는 방법을 경험할 수 있었다. 문제의 도전적인 측면은 각 단계에서의 최적의 결정을 찾고 이를 기반으로 전체 해결책을 구축하는 것이었다.