백준 1256: 사전 [Python 파이썬 / DP]

백준 1256: 사전

🥸 문제 분석

문제의 답으로 K번째 문자열을 찾아야 한다.
또한 K가 가능한 문자열 개수보다 크다면 -1을 출력해야 한다.
그래서 a N개, z M개로 만들 수 있는 문자열의 개수를 구할 필요가 있다.

☝️ 문제 풀이

1. 문자열 개수 구하기

처음에는 조합을 사용할까 고민했다.
그러나 a 100개, z 100개일 때 문자열의 조합을 모두 구하고 K번째를 찾기에는 경우의 수가 너무 많다는 생각이 들었다.

그럼에도 불구하고 DP로 풀어야겠다는 생각을 떠올리지는 못했는데,
문제 유형을 확인하고 과거에 비슷한 유형의 문제를 풀었던 기억이 떠올랐다.

a N개, z M개로 만들 수 있는 문자열은 작은 단위부터 생각해보자.

우선 N = 0, M = 1이라면?
'z', 단 하나만 가능하다.

반대로 N = 1, M = 0이라면?
'a', 단 하나만 가능하다.

그럼 N = 1, M = 1이면?
'az', 'za'가 가능할 것이다.

'az'부터 보자.
'az' = 'a' + 'z' 이다.
N = 0, M = 1인 경우는 'z' 였다.
여기서 N이 1 늘어난다는 것은,
a가 하나 더 추가된다는 의미이다.
즉, 'z'앞에 'a'를 이어줄 수 있게 되는 것과 같다.

'za'도 보자.
'za' = 'z' + 'a' 이다.
N = 1, M = 0인 경우에서
M이 1 늘어난 경우,
즉 z가 하나 더 추가된 경우이다.
이것은 'a'앞에 'z'를 이어줄 수 있게 된다.

N, M을 늘려가면서 예시를 조금 더 볼 수 있겠지만, 사실 위 예시를 통해 점화식은 이미 나왔다.

dp[N][M] <- a가 N개, z가 M개일 때 가능한 문자열의 경우의 수라고 생각하면,

위 예시를 통해 dp[1][1] = dp[1][0] + dp[0][1] 임을 알 수 있다.
즉 점화식은 dp[X][Y] = dp[X - 1][Y] + dp[X][Y - 1] 이다.

점화식을 통해 dp 배열을 초기화시켜주자,

for i in range(1, N + 1):
	for j in range(1, M + 1):
    	dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

위와 같은 코드를 작성할 수 있다.

2. K번째 문자열 찾기

이제 문자열의 개수를 알았으니 K번째 문자열이 대체 무엇인지를 알아내야 한다.
문자열을 먼저 구하고 개수를 센 것이 아니라, 단지 몇 가지 문자열이 가능한 지만 구했기 때문이다.
그럼 해당 문자열을 어떻게 구할 수 있을까? 답은 우리가 점화식을 얻어낸 과정에 있다.

dp[N][M] <- a가 N개, z가 M개일 때 가능한 문자열의 경우의 수라고 했다.
그럼 dp[N - 1][M]은 무슨 의미를 가질까? 맨 앞의 알파벳을 a로 고정시키겠다는 의미라고 볼 수 있다.

이해가 되지 않았다면 dp[1][1]을 다시 보자.
dp[0][1]은 'z' 였다.
dp[1][1]은 dp[0][1]에서 N값이 1 늘어난, a를 하나 더 쓸 수 있게된 경우의 수였고,
'z' 앞에 'a'를 이어준 것과 같았다.

즉 dp[N - 1][M]은 맨앞에 'a'를 이어서 dp[N][M]의 일부가 될 후보군인 것이다.
반대로 dp[N][M - 1]은 맨앞에 'z'를 이어서 dp[N][M]의 일부가 될 것이다.

백준 예시처럼 N = 2, M = 2, K = 2인 경우를 보자.

• N = 0, M = 0 -> 아무것도 없음
• N = 0, M = 1 -> z
• N = 1, M = 0 -> a
• N = 1, M = 1 -> N=0,M=1 + N=1,M=0 => a + z & z + a => az, za
• N = 2, M = 1 -> N=1,M=1 + N=2,M=0 => a + (az, za) & z + (aa) => aaz, aza, zaa
• N = 1, M = 2 -> N=0,M=2 + N=1,M=1 => a + (zz) & z + (az, za) => azz, zaz, zza
• N = 2, M = 2 -> N=1,M=2 + N=2,M=1 => z + (aaz, aza, zaa) & a + (azz, zaz, zza)
  => aazz, azaz, azza, zaaz, zaza, zzaa

위와 같이 문자열의 개수가 누적될 것이고, 이것을 거꾸로 찾아간다고 생각하면,
N = 2, M = 2, K = 2로 시작한다.
dp[1][2]은 dp[2][2]에서 aazz azaz azza가 될 문자들 3개 (azz, zaz, zza) 이다.
K는 2이므로 이 범위안에 들어간다. 그래서 문자열의 첫번째 알파벳은 a가 되고,
N에서 1을 빼준다. (a로 고정했다는 의미)

이제 다음으로 탐색할 범위인 dp[0][2]은
dp[1][2]에서 azz가 될 문자 1개 (zz) 인데, K는 2이므로 1보다 크다.
즉 dp[0][2]가 아니라, dp[1][1] => zaz zza가 될 문자들 2개 (az, za) 에 속하는 범위이다.
그래서 dp[0][2]에 속하는 문자들은 후보군에서 제외되고,
K에서 dp[0][2]의 개수인 1을 차감해준다.
문자열의 두번째 알파벳은 z가 되고, M은 1을 빼준다. (z로 고정했다는 의미)

이제 K=1 이고, dp[0][1]을 보자. dp[1][1]에서 az가 될 문자 1개 (z) 이다.
K가 1이기 때문에 해당 문자가 답이다.
즉 세번째 알파벳은 a고, N에서 1을 뺀다.

이 논리를 기반으로 코드를 작성해보자.

# 입력받은 N, M, K 그대로 사용
# N, M, K을 조금씩 감소 시키며 문자열의 첫자리부터 알파벳을 하나씩 고정해나간다.
answer = ''
while N > 0 or M > 0:
	split = dp[N - 1][M] # 현재 타겟 인덱스의 알파벳을 a로 고정했을 때, 후보가 될 수 있는 문자의 개수

	if K <= split: # 현재 인덱스의 알파벳이 a인데, 그 범위 안에 K가 속할 때
    	N -= 1 # a로 고정
        answer += 'a'
    else: # K가 더 큼 -> 현재 인덱스의 알파벳은 z가 되어야 함
    	M -= 1 # z로 고정
        K -= split # 현재 인덱스의 알파벳을 a로 갖는, K번째 문자열보다 앞서는 문자들을 후보에서 제거
        answer += 'z'
else: # N, M 둘중에 하나가 0이 되면 while문이 break되지만 아직 남은 N, M이 있음
	answer += ('a' * N + 'z' * M) # 남은 문자 이어주기

누적된 문자열을 출력하면 정답.