문제 링크
https://www.acmicpc.net/problem/1562
🛠️ 미해결
- 풀이시간 : 2시간 이상
🕒 Python 풀이시간: x
n=int(input())
dp=[[[-1]*(1024) for _ in range(10)] for _ in range(101)]
def showbit(bit):
k=""
for i in range(9,-1,-1):
if bit&(1<<i):
k+="1"
else:
k+="0"
return k
def dfs(now,deep,bit):
if deep==n:
allExist=True
for i in range(10):
if not (bit>>i)&1:
allExist=False
if allExist:
dp[deep][now][bit]=1
return 1
dp[deep][now][bit]=0
return 0
dp[deep][now][bit]=0
if now+1<10:
if dp[deep+1][now+1][bit|1<<(now+1)]!=-1:
dp[deep][now][bit]+=dp[deep+1][now+1][bit|1<<(now+1)]
else:
dp[deep][now][bit]+=dfs(now+1,deep+1,bit|1<<(now+1))
if now-1>=0:
if dp[deep+1][now-1][bit|1<<(now-1)]!=-1:
dp[deep][now][bit]+=dp[deep+1][now-1][bit|1<<(now-1)]
else:
dp[deep][now][bit]+=dfs(now-1,deep+1,bit|1<<(now-1))
return dp[deep][now][bit]
cnt=0
for i in range(1,10):
cnt+=dfs(i,1,0|1<<i)
print(cnt%1000000000)계단 수의 세계: N자리 숫자 조합의 비밀을 파헤치다! 🚀
연속된 0~9로 한자리가 이루어진 수가 N자리 나열될 경우, 다음에 올 수가 1씩 차이 날 경우에 이 수를 계단 수라고 하는데 이러한 가능한 N자리 수의 갯수를 구하는 문제이다.
재귀를 통해서 간단하게 줄일 수 있는 문제이다. 먼저 DFS 식을 구성한 다음 이를 DP로 연결 시켜주면 된다. 이때, dp가 분리되는 조건을 따지느라 시간이 꽤 오래걸렸다. 처음에는 bit와 deep으로만 계산을 하였지만 이러한 경우는 현 상황의 조건을 dp에 완전히 반영하지 못하기 때문에 불가능하였다. 즉, dp가 부분 해를 가지고 현재의 해를 구하는 것인데 해당 해가 어떤 상황에서 발생하는 해인지가 불확실하거나 중복되어 문제가 된 것이다. 그렇기 때문에 3차원 배열로 모든 조건을 반영하여 배열을 구성하였다.
현재의 수보다 +1, -1인 수가 있는지 탐색해 들어가는데 이미 그 해를 구한 적이 있다면 단순히 지금의 해를 더하고 아니라면 dfs를 시행하여 수를 구해오는 것이다. 그렇게 수행한 해를 마지막으로 return 시켜주면 된다. 0은 불가능하기 때문에 0을 제외한 1~9까지의 수들을 전부 탐색하면서 수들을 전부 더해주면 답을 구할 수 있다.
이렇게 Python으로 백준의 "계단 수" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
