[백준] 19844 쉬운 계단

1. 문제

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

10844번: 쉬운 계단 수

 

2. 풀이

 

후하후하 이거 어떻게 DP로 풀어야하나 했는데 ㅠㅠ

전혀 검색을 안해서 순전히 내생각으로 해보자면

 

1) 내가 지나가야하는 숫자들

2) 지나간 숫자들을 같은 인덱스로 또 다음 후보군으로 만났을때 그 수를 저장

 

이 두가지를 저장하는 느낌으로?

 

1. 위 말한 저장할 변수 두 가지를 선언한다. (대신 count변수는 첫째자리 바뀔때마다 매번 초기화)

2. 이제 첫째 자리(index=0)부터 시작한다. (1~9만 가능) ==> queue 선언해서 (i, 0) 로 시작

3. next 가 빌때까지 계속돈다. ==> 약간의 (ㅎ_ㅎ) BFS 응용

4. next를 pop해서 (n=숫자, idx=몇번째자리인지) 추출한다.

5. 이때 만약 idx가 n-1이면 이제 개수를 세는데, 이 뒤로는 100% 다 같은 인덱스라 여기서 다 돌고 while을 나가준다.

6. 마지막 인덱스가 아니라면, 현재 수와 1 차이나는 다음 수들을 idx+1해서 next에 추가해준다.

7. 추가할때, 이전에 이미 같은 수가 같은 인덱스로 한 번 들어온적이 있다면, 현재 수의 등장횟수를 count에 더해주고, 아니면 새로 1로 딕셔너리에 생성해준다.

==> 이때 만난적 있던 경우엔 next에 추가안해준다.

 

## code ##

import sys, collections

nn = int(sys.stdin.readline())
total = 10**(nn)
cnt = 0

## 시작은 1~9 까지만 가능
for i in range(1, 10):

    ## DP 처럼 사용할 딕셔너리 선언: 0-9까지 숫자가 몇번째 index가 몇 번 나왔는지
    count = {}
    for j in range(10):
        count[j] = collections.defaultdict(int)

    ## 시작은 i, index는 0번째
    next = collections.deque([(i, 0)])
    count[i][0] = 1

    ## 약간의 BFS 응용으로 next(다음 1 차이나는 숫자 후보군) 빌때까지
    while next:
        # print(next, cnt)
        # print(count)
        n, idx = next.popleft()

        ## index가 n-1자리인거 만나면 거기서부터 남은 next는 다 n-1 index일거라 다 세기
        if idx == nn - 1:
            next.appendleft((n, idx))
            for item in next:
                n, idx = item
                c = count[n][idx]
                if idx == 0:
                    cnt += 1
                else:
                    cnt += c
            break
        
        ## 1, 9는 1 차이 수가 하나씩이라 다른것만
        if n != 0 and n!=9:
            if n - 1 >= 0:
                
                ## 이미 이 좌표를 같은 인덱스로 지나친적 있으면 그냥 합쳐주기
                if count[n-1][idx+1]:
                    count[n-1][idx+1] += count[n][idx]
                else: # 아니면 이전의 자리의 개수 넘겨주기
                    count[n - 1][idx + 1] = count[n][idx]
                    next.append((n-1, idx+1))
                    
            if n + 1 < 10:
                if count[n+1][idx+1]:
                    count[n+1][idx+1] += count[n][idx]
                else:
                    count[n + 1][idx + 1] = count[n][idx]
                    next.append((n+1, idx + 1))

        elif n == 0:
            if count[n + 1][idx + 1]:
                count[n + 1][idx + 1] += count[n][idx]
            else:
                count[n + 1][idx + 1] = count[n][idx]
                next.append((n+1, idx+1))

        elif n == 9:
            if count[n - 1][idx + 1]:
                count[n - 1][idx + 1] += count[n][idx]
            else:
                count[n - 1][idx + 1] = count[n][idx]
                next.append((n-1, idx+1))
print(cnt%1000000000)

 

아싸!!!!!!!!!!!