우매함의 봉우리를 넘어서며 개발하면서 기록하기

백준 1256. 사전 문제풀이(dp, 수학)

29 Mar 2022

문제 바로가기

사전

문제 요약

“a” n개와 “z” m 개로 이루어진 문자열 중 k 번째에 위치한 문자열을 구하는 문제이다.

문제 풀이 포인트

이 문제는 다음과 같은 두 가지 개념을 나누어 풀었습니다.

  1. 경우의 수 구하기
  2. k 번째 문자열 찾기 나누어 설명하겠습니다. 말과 그림으로는 설명하기 쉬운데 글로 적으면 어려우니 혹시 이해가 가지 않으면 질문해주세요.

1. 경우의 수 구하기

풀이의 fill() 메서드의 동작 과정입니다.

알파벳 a n 개와 알파벳 z m 개가 있을 때 만들 수 있는 문자열의 경우의 수를 구하는 방법은 다음과 같습니다.

(n + m)! / (n! * m!) -> 원리는 같은것이 있는 순열 검색하시면 됩니다.

이 순열의 계산 값을 dp 배열에 저장합니다. 예를 들어, n = 3, m = 2 라면 dp 배열은 다음 표와 같은 형태로 저장될 것입니다.

  m=0 m=1 m=2
n=0 0 1 1
n=1 1 2 3
n=2 1 3 6
n=3 1 4 10

이 에서 dp[3][2] 의 값은 a 와 z 로 만들 수 있는 모든 문자열의 개수를 의미합니다. 그 의미는 이 값으로 k 와 비교하여 가능한지 비교할 수 있다는 의미와 동일합니다.

2. k 번째 문자열 찾기

풀이의 makeString() 메서드의 동작 과정입니다.

위의 표에서 dp[3][2]의 의미는 앞에서 살펴봤기 때문에 제외하고 다른 값들의 의미를 살펴보자면 dp[2][2] 는 a 2개와 z 2개로 만들 수 있는 문자열의 개수입니다. 그 의미는 문자열의 첫번째 자리가 a라고 할 때 만들 수 있는 문자열의 개수와 같습니다.

aXXXX 에서 a 2 개와 z 2개를 넣어 만들 수 있는 문자열

dp[3][1] 은 마찬가지로 a 3개와 z 1개로 만들 수 있는 문자열의 개수입니다. 즉, 문자열의 첫번째 자리가 z 인 문자열의 개수입니다.

이 개념을 이용하여 dp[n][m] 부터 거슬러 올라가며 문자열을 만들어 줄겁니다. 사전의 형태이므로 항상 a 가 z 보다 먼저 와야 합니다. 그렇다면, 우리는 먼저 dp[n - 1][m] 을 바라봅니다.

  1. 이 숫자가 k 보다 크다면 k 번째 문자열의 시작은 a 로 시작합니다.
  2. 이 숫자가 k 보다 작다면, 즉 k 가 더 크다면 k 번째 문자열은 z 로 시작합니다.
  3. 위의 과정을 반복하여 n 또는 m 중 하나가 0 이 된다면 남은 개수만큼 a 또는 z 를 뒤에 추가합니다.
    • n 이 남을 경우 a 를 추가합니다.
    • m 이 남을 경우 z 를 추가합니다.

이때 한 가지 주의해야 할 점은 각 값은 남은 개수로 만들 수 있는 개수를 뜻합니다. 하지만, k 값은 전체 개수에서 몇 번째인지 바라보고 있습니다. 그 말은, z 로 시작하는 문자열인 경우 k 의 값은 재조정이 필요하다는 것입니다. 이미 z 로 시작하는 문자열임을 알았기에 전체 개수 중 a 로 시작하는 문자열의 개수를 빼야 z 로 시작하는 문자열 중 몇 번째인지 확인할 수 있습니다.

예를 들어, 같은 예시에서 k = 7 인 문자열을 찾아보겠습니다. (n = 3, m = 2)

  1. (n = 3, m = 2, k = 7) dp[2][2]를 가지고 비교했을 때 dp[2][2] < k 이므로 문자열은 z 로 시작합니다. 그럼 z 로 시작하는 문자열 중 첫 번째 문자열 중 첫 번째 문자열과 같습니다. (k = k - dp[2][2] = 1, m = 1)
  2. (n = 3, m = 1, k = 1) dp[2][1] 과 k 를 비교하면 dp[2][1] >= k 이므로 문자열은 za 가 됩니다.
  3. (n = 2, m = 1, k = 1) dp[1][1] 과 k 를 비교하면 dp[1][1] >= k 이므로 문자열은 zaa 가 됩니다.
  4. (n = 1, m = 1, k = 1) dp[0][1] 과 k 를 비교하면 dp[0][1] >= k 이므로 문자열은 zaaa 가 됩니다.
  5. (n = 0, m = 1, k = 1) n 이 0이 되었으므로 남은 m 의 개수만큼 z 를 추가합니다. 따라서 최종 문자열은 zaaaz 가 됩니다.

문제 코드[JAVA]

코드 펼치기 
import java.util.*;

public class Main {
  private static int[][] dp;
  private static final int MAX = 1000000000;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int k = sc.nextInt();

    dp = new int[n + 1][m + 1];

    int count = fill(n, m);
    if (count < k) {
      System.out.println(-1);
    } else {
      makeString(n, m, k);
    }
  }

  private static void makeString(int n, int m, int k) {
    StringBuilder sb = new StringBuilder();
    while (n != 0 && m != 0) {
      int num = dp[n -1][m];
      if (num < k) {
        sb.append("z");
        k -= num;
        m -= 1;
      } else {
        sb.append("a");
        n -= 1;
      }
    }

    if (n == 0) {
      while (m-- > 0) {
        sb.append("z");
      }
    } else {
      while (n-- > 0) {
        sb.append("a");
      }
    }

    System.out.println(sb);

  }

  private static int fill(int n, int m) {
    if (n == 0 || m == 0) return dp[n][m] = 1;
    if (dp[n][m] != 0) return dp[n][m];

    return dp[n][m] = Math.min(fill(n - 1, m) + fill(n, m - 1), MAX);
  }
}

Related posts