[백준 - 12969번] ABC - Java

문제 링크

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

문제

티어: 골드 1
알고리즘: dp
정수 N과 K가 주어졌을 때, 다음 두 조건을 만족하는 문자열 S를 찾는 프로그램을 작성하시오.

• 문자열 S의 길이는 N이고, 'A', 'B', 'C'로 이루어져 있다.
• 문자열 S에는 0 ≤ i < j < N 이면서 S[i] < S[j]를 만족하는 (i, j) 쌍이 K개가 있다.

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 30, 0 ≤ K ≤ N(N-1)/2)

출력

첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다.

풀이

문제의 조건을 만족하는 문자열 S를 출력해야 한다.

길이가 2인 상태에서 K가 1인 경우를 나열해 보면
AB, AC, BC 이렇게 세 가지 존재한다.

그리고 길이가 3인 상태에서 K가 2인 경우를 나열해 보면,
ABB, ACB, ACC, BCC 이렇게 네 가지 존재한다.

잘보면 AB, AC, BC에 A, B, C가 추가된 형태임을 알 수 있다.
그러니까 K가 증가하기 위해서는 맨 뒤에 A, B, C가 추가되어야 하고, 추가되었을 때 K의 개수는 기존 문자열이 어떤 문자로 구성되어 있는지로 알 수 있다.

예를 들어 AB는 A 1개, B 1개이다. 이 때 B가 추가된다면, B보다 사전 순으로 빠른 A만이 조건을 만족하는 쌍을 만들 수 있기 때문에 ABB의 K는 2개가 되는 것이다.

그러면 고유한 경로를 판단하기 위해서는 각 문자의 개수로만 판단하면 될까?
예를 들어 AB, BA가 있다고 하자 각 문자의 구성은 같아서 이후 탐색은 같다고 해도 K가 다름을 알 수 있다. AB는 1이고, BA는 0이다.

그래서 고유한 경로를 판단하기 위해서는 추가적으로 K가 필요하다.

이를 토대로 dp를 정의하면 4차원 배열이 된다. dp[A][B][C][K]
A -> A는 A의 개수다.
B -> B는 B의 개수다.
C -> C는 C의 개수다.
K -> K는 현재 문자열의 K의 개수다.

그래서 boolean dp를 이용해서 빈 문자열부터 A, B, C를 추가하면서 경로를 탐색하고, 중복 경로는 탐색하지 않으면서 백트래킹을 하는 방식으로 문제의 답을 구해줄 수 있다.
자세한 구현 방법은 코드를 참고하길 바란다.

이 풀이의 시간 복잡도는 O(30 30 30 * 435)다.

소스 코드

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

public class Main {
    static final char[] arr = {'A', 'B', 'C'};
    static final int[] da = {1, 0, 0};
    static final int[] db = {0, 1, 0};
    static final int[] dc = {0, 0, 1};
    static final StringBuilder sb = new StringBuilder();
    static int N, K;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      K = Integer.parseInt(st.nextToken());
      boolean[][][][] visited = new boolean[31][31][31][436];
      if(dfs(0, 0, 0, 0, visited)) {
          System.out.println(sb.toString());
      } else {
          System.out.println(-1);
      }
  }
  
  static boolean dfs(int a, int b, int c, int k, boolean[][][][] visited) {
      if(!checkRange(a, b, c, k)) {
          return false;
      }
      
      if(visited[a][b][c][k]) {
          return false;
      }
      
      visited[a][b][c][k] = true;
      if(((a + b + c) == N) && (k == K)) {
          return true;
      }
      
      for(int i=0; i<3; i++) {
          int nK = calNextK(a, b, c, k, i);
          sb.append(arr[i]);
          if(dfs(a + da[i], b + db[i], c + dc[i], nK, visited)) {
              return true;
          }
          sb.deleteCharAt(sb.length() - 1);
      }
      return false;
  }
  
  static boolean checkRange(int a, int b, int c, int k) {
      if(a <= 30 && b <= 30 && c <= 30 && k <= 435) {
          return true;
      }
      return false;
  }
  
  static int calNextK(int a, int b, int c, int k, int std) {
      int result = k;
      if(std == 1) {
          //맨 끝에 B가 추가됨
          result += a;
      } else if(std == 2) {
          //맨 끝에 C가 추가됨
          result = result + (a + b);
      }
      return result;
  }
}