[백준 1594] 전화번호 만들기 - JAVA

https://www.acmicpc.net/problem/1594

 

dp

 

일반 dp는 i번째까지 구성했을 때 값이나 컨디션만 필요하다. 근데 이 문제는 경로도 요구한다.

따라서, dp와 path 배열을 같이 기록해준다.

 

dp[i-2] or dp[i-3] 에 대해,

더 높은 값(품질)을 얻을 수 있거나, 똑같은 값이어도 path를 사전 순으로 앞당길 수 있다면 갱신한다.

 

배낭 문제 + 역추적으로 풀어보려 했었는데, 되는지 확신을 가지지 못해서 경로를 직접 저장했다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  static String number;
  static int n;
  static int[] dp; // 품질 저장
  static String[] path; // 품질 최대일 때의 문자열 저장

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    number = sc.next();
    n = number.length();

    dp = new int[n + 1];
    Arrays.fill(dp, -1);
    dp[0] = 0;

    path = new String[n + 1];
    path[0] = "";

    for (int i = 2; i <= n; i++) {
      // 2자리 그룹
      String group2 = number.substring(i - 2, i);
      int score2 = score(group2);
      if (dp[i - 2] != -1) {
        int newScore = dp[i - 2] + score2;
        String newPath = path[i - 2].isEmpty() ? group2 : path[i - 2] + "-" + group2;
        if (dp[i] < newScore || (dp[i] == newScore && newPath.compareTo(path[i]) < 0)) {
          dp[i] = newScore;
          path[i] = newPath;
        }
      }

      // 3자리 그룹
      if (i >= 3) {
        String group3 = number.substring(i - 3, i);
        int score3 = score(group3);
        if (dp[i - 3] != -1) {
          int newScore = dp[i - 3] + score3;
          String newPath = path[i - 3].isEmpty() ? group3 : path[i - 3] + "-" + group3;
          if (dp[i] < newScore || (dp[i] == newScore && newPath.compareTo(path[i]) < 0)) {
            dp[i] = newScore;
            path[i] = newPath;
          }
        }
      }
    }

    System.out.println(path[n]);
  }

  static int score(String group) {
    if (group.length() == 2) {
      return group.charAt(0) == group.charAt(1) ? 2 : 0;
    } else {
      char a = group.charAt(0), b = group.charAt(1), c = group.charAt(2);
      if (a == b && b == c) {
        return 2;
      }
      if (a == b || b == c || a == c) {
        return 1;
      }
      return 0;
    }
  }
}