백준 문제 1256번 사전 문제풀이 python

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

1256번: 사전

 

문제해석

규칙같은게 있나 찾아보기위해 몇개 정도 나열해보자면

n=1,m=0 일때

만들수 있는 단어는

a

1개

n=0,m=1 일때

z

1개

n=1,m=1 일때

az
za

2개

n=1,m=2일때

azz
zaz
zza

3개

n=2,m=1일때

aaz
aza
zaa

3개

n=2,m=2일때

aazz
azaz
azza
zaaz
zaza
zzaa

6개

...

...

 

즉 dp[i][j]를 a갯수 i개 z갯수 j개로 만들수 있는 단어의 개수라고 정의를 하면 dp[i][j]=d[i-1][j]+dp[i][j-1]식을 만족한다.

이 식은 이항계수 혹은 파스칼의 삼각형에서 자주 보았던 식이라 익숙한 모습이다.

 

입력값이 100*100까지 이므로 dp[1][1]부터 dp[100][100]까지의 값을 세팅 해준 후 재귀적으로 해결을 해야한다.

 

재귀 함수를 작성하기위한 기저 조건을 먼저 살펴보자

k>dp[n][m] 일때 k번째 문자열이 당연히 존재하지않으므로 종료

n이 0일때 m개의 z를 붙여주고 종료

m이 0일때 n개의 a를 붙여주고 종료

 

위에서 말한 경우 외에는 dp[n][m]=dp[n-1][m]+dp[n][m-1] 이므로

case1 : 1<= k <=dp[n-1][m]일때와

case2 : dp[n-1][m] < k일때 경우로 나눌 수 있다.

 

case1 일때는 dp[n-1][m]의 문자에 맨앞에 a문자를 붙이면 되고

case2 일때는 dp[m][n-1]의 문자에 맨앞에 z문자를 붙이면 된다.

 

이해가 잘 안될거 같아서 예시를 들면

설명을 위한 dp2[i][j]를 i개 a , j개 z로 만들수있는 문자열의 집합으로 잠깐 정의를 해주면

 

dp2[2][2]는

aazz
azaz
azza
zaaz
zaza
zzaa

인데 파란색 부분은 dp2[1][2]이고 보라색 부분은 dp2[2][1]의 부분이다.

즉, 1<= k <= 3 (dp[1][2]) 일때는 맨 앞에 a 문자 추가

3 (dp[1][2]) < k 일때는 맨앞에 z 추가 임을 확인 할 수 있고 다른 i , j에 대해서도 당연히 성립한다.

 

이 문제를 파이썬으로 작성한 이유는 dp[100][50]같은경우 c++의 long long int 형을 넘는 큰수가 되기 때문에

큰 수 처리를 따로 하지 않기 위해 파이썬을 사용했다.

 

코드

ans=""
def solve(n,m,k):
    global ans
    if a[n][m]<k:
        return
    if n==0:
        for i in range(0,m):
            ans=ans+"z"
        return
    elif m==0:
        for i in range(0,n):
            ans=ans+"a"
        return
    else:
        left=a[n-1][m]
        if 1<=k and k<=left:
            solve(n-1,m,k)
            ans="a"+ans
        elif left<k:
            solve(n,m-1,k-left)
            ans="z"+ans
        return

a=[[0 for col in range(101)] for row in range(101)]
for i in range(0,101):
    a[i][0]=1
    a[0][i]=1
for i in range(1,101):
    for j in range(1,101):
        a[i][j]=a[i-1][j]+a[i][j-1]
s=input()
l=s.split()
n=int(l[0])
m=int(l[1])
k=int(l[2])
solve(n,m,k)
if ans=="":
    print("-1")
else:
    print(ans)

 

ans=""
def solve(n,m,k):
    global ans
    if a[n][m]<k:
        return
    if n==0:
        for i in range(0,m):
            ans=ans+"z"
        return
    elif m==0:
        for i in range(0,n):
            ans=ans+"a"
        return
    else:
        left=a[n-1][m]
        if 1<=k and k<=left:
            ans=ans+"a"
            solve(n-1,m,k)
        elif left<k:
            ans=ans+"z"
            solve(n,m-1,k-left)
        return

a=[[0 for col in range(101)] for row in range(101)]
for i in range(0,101):
    a[i][0]=1
    a[0][i]=1
for i in range(1,101):
    for j in range(1,101):
        a[i][j]=a[i-1][j]+a[i][j-1]
s=input()
l=s.split()
n=int(l[0])
m=int(l[1])
k=int(l[2])
solve(n,m,k)
if ans=="":
    print("-1")
else:
    print(ans)

 

첫번째 코드가 위에서 설명한 방식으로 코드를 작성한 것 이고

 

두번째 코드는 위에서 설명한 방식은 아니지만 비슷한 아이디어로 푼것이다. 둘다 AC를 받는다.