[백준 / BOJ] 1256 사전

문제

출처 : www.acmicpc.net/problem/1256

1256번: 사전

"a","z"로만 이루어진 문자열이 수록된 사전이있다.

사전에 있는 문자열은 모두 알파벳 순서로 정렬되어있다.

"a"의 갯수 N, "z"의 갯수 M이 주어질때, K번째 문자열이 무엇인지 찾는 문제다.

 

풀이

수학 문제였다.

N과 M이 각각 100까지 갈수있기때문에. 완전탐색으로 모든 가지를 만들며 풀경우 약 10^60번 반복하며 시간안에 절대 풀지못한다.

 

조합을 이용해 찾고자하는 칸 만큼 건너뛰면서 K번째 문자열을 찾아야했다.

아이디어는 다음과 같다.

 

1. 현재 경우에서 "a"를 붙이는 경우와 "z"를 붙이는 경우 두가지로 나누어 생각했다.

- "a"를 붙이는 경우, 문자열 ~a 뒤에 올수있는 모든 경우의수는 ((N-1)+M)C(N-1) 이 된다.

- "z"를 붙이는 경우, 문자열 ~z 뒤에 올수있는 모든 경우의수는 (N+(M-1))C(M-1) 이 된다.

 

2. K번째 문자열을 찾기위해선 K-1개의 문자열을 스킵해야한다.

- 1번의 "a"를 붙이는 경우를 가지고 이 를 수행할수있는데, 만약 a를 붙인후 나오는 경우의수인 ((N-1)+M)C(N-1) 이 K보다 작다면, K번째 문자열을 찾기위해선 현재 위치에서 무조건 "z"를 붙여야 한다. 이 때, "z"를 붙이는 경우 K에서 ((N-1)+M)C(N-1)만큼을 스킵한것이므로 K = K - ((N-1)+M)C(N-1) 이 된다.

 

위 두가지 경우를 구현하면 된다.

 

코드를 더 빠르게 수행시키기 위해서 다이나믹 프로그래밍을 이용해 모든 조합을 구해놓고 탐색했는데, N과 M이 각각 100까지 갈수있으므로 다이나믹 프로그래밍을 사용하지 않더라도 시간초과는 안날것같다 (아마도)

다이나믹 프로그래밍을 사용하지않을경우, 매 탐색마다 조합을 구하는데 약 N+M번 반복하고, 모든 문자열을 만드는데 N+M번 반복하므로, 시간복잡도는 O((N+M)^2)이 될것이다.

 

다이나믹 프로그래밍을 사용할경우 시간복잡도는 O(N+M)이 된다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1256%20%EC%82%AC%EC%A0%84/main.cpp

devxb/JJUNalgo