[Java] BOJ1256, 백준 - 사전

2022. 4. 11. 23:54·알고리즘/문제풀이
728x90

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

 

1256번: 사전

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되

www.acmicpc.net

n, m, k가 주어졌을 때 가능한 순서의 총 경우의 수는 전체 경우의 수를 중복되는 a와 z의 수로 나눈 (n+m)!/(n!m!)이다.
이를 바탕으로 n+m자리의 문자열을 만들 때, dp방식으로 접근.
예를 들어서
첫 번째 문자열의 경우의 수는 총 (n+m)!/(n!m!)
첫 번째 문자가 a였다고 가정했을 때, 그 다음은
a + (n+m-1)!/((n-1)!m!)
두 번째 문자도 a라고 가정하면
aa + (n+m-2)!/((n-2)!m!)
와 같은 형식으로 진행된다.

그렇다면 문자가 a인지 z인지는 어떻게 판단하는가?
n+m자리 문자열을 만드는 경우는
a+ (n+m-1)!/((n-1)!m!)의 경우와 z + (n+m-1)!/(n!(m-1)!)의 경우를 합친 경우일 것이다.
문자열이 사전 순으로 만들어지기 때문에 (n+m)!/(n!m!)중에서 (n+m-1)!/((n-1)!m!)번째 수 까지의 문자열은 a가 되고 나머지는 z가 된다.
즉, 점화식은 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이고
문자열은 k와 dp[n - 1][m]를 비교해주면 a인지 z인지 알 수 있게 된다.

*점화식에 대한 간단한 증명

 

*소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ1256 {
    private static int[][] dp;
    private static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = parse(st.nextToken()); // a개수
        m = parse(st.nextToken()); // z개수
        int k = parse(st.nextToken());

        fillArr();

        if (k > dp[n][m]) {
            System.out.println(-1);
            return;
        }

        StringBuilder sb = new StringBuilder();
        // k번째 수 구하기
        while (n > 0 || m > 0) {
            int a = (n <= 0) ? 0 : dp[n - 1][m];

            if (k <= a) {
                // a를 이어붙이면 됨
                n--;
                sb.append("a");
            } else {
                m--;
                k -= a;
                sb.append("z");
            }
        }
        System.out.println(sb.toString());
    }

    private static void fillArr() {
        dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + dp[i][j - 1], 1000000001);
            }
        }
    }

    private static int parse(String s) {
        return Integer.parseInt(s);
    }
}
저작자표시 (새창열림)

'알고리즘 > 문제풀이' 카테고리의 다른 글

백준4179 : 불!  (0) 2023.09.19
백준17106 : 빙고  (0) 2023.06.20
[Java] 프로그래머스 - 전력망을 둘로 나누기  (0) 2022.04.05
[Java] BOJ20364, 백준 - 부동산 다툼  (0) 2022.03.09
[Java] BOJ16562, 백준 - 친구비  (0) 2022.02.25
'알고리즘/문제풀이' 카테고리의 다른 글
  • 백준4179 : 불!
  • 백준17106 : 빙고
  • [Java] 프로그래머스 - 전력망을 둘로 나누기
  • [Java] BOJ20364, 백준 - 부동산 다툼
kkap999
kkap999
IT에 관심 가득한 갑갑이의 개발&스터디 블로그
  • kkap999
    갑갑이의 개발세상
    kkap999
    • 분류 전체보기 (95)
      • Backend (1)
        • Java&Spring&Servlet (8)
        • DB (0)
      • 알고리즘 (78)
        • 문제풀이 (70)
        • 자료구조 (6)
        • 그 외 (2)
      • App&FE (3)
        • FE (1)
        • Flutter (2)
      • Computer Science (0)
        • 네트워크 (0)
        • 컴퓨터기초 (0)
      • Cloud (0)
        • AWS (0)
        • Azure (0)
        • gcp (0)
      • 잡담&일상 (4)
        • 일상 (1)
        • 잡담 (2)
        • 음악 (1)
  • 태그

    알고리즘
    백준
    BOJ
    BOJ15649
    N과M(1)
  • 링크

    • github
  • 인기 글

  • 최근 글

  • 07-20 07:30
  • 전체
    오늘
    어제
  • 반응형
  • hELLO· Designed By정상우.v4.10.3
kkap999
[Java] BOJ1256, 백준 - 사전

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.