[파이썬] 백준 1562: 계단 수 (골드1)

[파이썬] 백준 1562: 계단 수 (골드1)

 

1562번: 계단 수

 

---

문제

---

풀이

0. 방향성 생각

생각을 조금 다르게 해서 접근. 3차원 DP 리스트 만들어서 풀이

 

비유를 하자면 달리기 0층에서 달리는 선수가 3층 끝에 도달하는 경우의 수를 카운트.

0번 레인, 9번 레인에는 엘베가 있다고 생각하면 된다. 한 번이라도 접근했으면 다음 층으로 이동.

리스트를 4 * 10 * n 형태로 만든다. 4는 층의 개수. (0~3층) / 10은 사용 가능한 lane 수 / n은 달려야할 거리.

 

0층은 아직 0번레인 9번레인을 선택하지 않은 사람

1층은 0번 레인을 선택해서 다음 층으로 올라간 사람

2층은 9번 레인을 선택해서 0층에서 올라온 사람

3층은 0번,9번 레인 둘 다 이용해서 올라온 사람

 

이후 3층 끝에 몇명이 도달하는지 보면된다.

 

일단 초반 입력에 대해서 맞게 나오는지 확인하려고 BFS로 작성한 코드로 결과 비교했음.

from collections import deque

n = int(input())

count = 0
check = set(range(10))
q = deque()
q.extend(['1','2','3','4','5','6','7','8','9'])
while q:
    x = q.popleft()
    if len(x) == n :
        temp = set(list(map(int,x)))
        if temp == check :count += 1
    else :
        for nx in ('0','1','2','3','4','5','6','7','8','9'):
            if abs(ord(x[-1])-ord(nx)) == 1:
                s = x + nx
                q.append(s)
print(count%10**9)

n자리수 만들고 나서 list -> set으로 바꾼다음에 0~9 들어있는 check 집합이랑 같으면 다 카운트.

n<=18 정도까진 금방 나오는듯

 

1. 입력

n = int(input())
k = 10**9
dp = [[[0]*10 for _ in range(n)] for i in range(4)]
dp[0][0] = [0]+[1]*8 +[0]
dp[2][0] = [0]*9+[1]

1~8번 출발하는 사람은 0층에서 출발한다. 1로 초기화

9번은 시작부터 9번레인 밟아서 2층 9번레인에서 시작한다.

 

2. DP

for h in range(4):
    for dist in range(n-1):
        for lane in range(10):
            
            if 0 < lane < 9:
                dp[h][dist+1][lane] += (dp[h][dist][lane-1]+dp[h][dist][lane+1])%k
                
            elif lane == 0 :
                if h==0: dp[1][dist+1][0] += dp[0][dist][1]%k
                elif h==2: dp[3][dist+1][0] += dp[2][dist][1]%k
                else : dp[h][dist+1][0] += dp[h][dist][1]%k
                    
            else :
                if h==0: dp[2][dist+1][9] += dp[0][dist][8]%k
                elif h==1: dp[3][dist+1][9] += dp[1][dist][8]%k
                else : dp[h][dist+1][9] += dp[h][dist][8]%k
                    
print(sum(dp[3][-1])%k)

 

• 1~8번 레인

1~8번 레인은 양 옆 레인에서 오는 경우의 수를 더해준다.

 

• 0번 레인

0번 레인은 사람이 항상 1번에서 온다.

0층에서 0번 레인으로 가면 1층으로 이동한다.

2층에서 0번 레인으로 가면 3층으로 이동한다.

 

• 9번 레인

9번 레인은 사람이 항상 8번에서 온다.

0층에서 9번 레인으로 가면 2층으로 이동한다.

1층에서 9번 레인으로 가면 3층으로 이동한다.

---

전체코드

n = int(input())
k = 10**9
dp = [[[0]*10 for _ in range(n)] for i in range(4)]
dp[0][0] = [0] + [1]*8 + [0]
dp[2][0] =  [0]*9 + [1]

for h in range(4):
    for dist in range(n-1):
        for lane in range(10):
            
            if 0 < lane < 9:
                dp[h][dist+1][lane] += (dp[h][dist][lane-1]+dp[h][dist][lane+1])%k
                
            elif lane == 0 :
                if h==0: dp[1][dist+1][0] += dp[0][dist][1]%k
                elif h==2: dp[3][dist+1][0] += dp[2][dist][1]%k
                else : dp[h][dist+1][0] += dp[h][dist][1]%k
                    
            else :
                if h==0: dp[2][dist+1][9] += dp[0][dist][8]%k
                elif h==1: dp[3][dist+1][9] += dp[1][dist][8]%k
                else : dp[h][dist+1][9] += dp[h][dist][8]%k
                    
print(sum(dp[3][-1])%k)

 

 

비트마스킹 풀이

n = int(input())
dp = [[[0]*10 for _ in range(n)] for _ in range(2**10)]

for i in range(1,10):
    dp[1<<i][0][i] = 1

k = 10**9
for state in range(2**10):
    for stage in range(n-1):
        for num in range(10):
            if num != 0:
                dp[state|(1<<num)][stage+1][num] += dp[state][stage][num-1]%k
            if num != 9:
                dp[state|(1<<num)][stage+1][num] += dp[state][stage][num+1]%k

print(sum(dp[-1][-1])%k)

기본적으로 state 나누는거는 같은데 state가 on/off 두가지가 10개있어서 2^10
스터디 코드 공유하면서 보니까, DP 순회할 때 한 노드 기준으로 들어오는거 모두 처리하는게 아니라 증가방향 / 감소방향 나눠푸는 사람이 많아서 이렇게 풀어봤는데 가독성이 훨씬 좋은듯.

 

계단수, 쉬운 계단수는 0부터 시작안하는데 변형 계단수가 0부터 시작해도 돼서 dp 초기화를 잘못시켜서 삽질좀 했음

 

코멘트

내가 풀었으니까 골1 문제는 아닌듯. +태그에 집착해서 풀지말기