[백준] 1038 - 감소하는 수(G5) : DP, BFS 풀이

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

1038번: 감소하는 수

쓸데없이 힘들게 푼 문제이다.

알고리즘 분류가 백트래킹에 브루트포스였는데, 그렇게 풀었으면 더 쉽게 풀었을 것 같다.

전체 경우의 수가 1023가지 밖에 되지 않아서, 그냥 모든 케이스를 순서대로 방문해보면 된다.

각 숫자가 중복으로 쓰일 수 없어서 비트마스킹을 활용한 풀이도 있었다.

 

나는 DP 에 역추적을 써서 풀었다.

정말 빙빙 돌아서 풀었다 ㅋㅋㅋ

 

내가 푼 풀이는 2차원 DP 테이블을 아래 정의로 만든다.

 

dp[i][j] = i자리 숫자중 첫번째 자리가 j로 시작하는 감소하는 수의 개수

 

그럼 dp[i][j] = dp[i-1][j-1] + dp[i][j-1] 점화식을 이용해 DP테이블을 채울 수 있다.

이 DP 테이블의 값을 이용해 역추적을 통해 답을 구하고자 하였다.

 

dp 테이블을 (0,0) 부터 시작해 카운트를 dp테이블 값만큼 늘려나가다가

만약 카운트가 찾는 숫자 이상이 되면, 그 순간의 길이와 첫 자리가, 정답인 숫자의 길이와 첫 자리가된다.

그 다음 자리의 숫자를 찾기 위해

 

(찾는 수 - 찾는 수를 넘기 직전의 카운트) + 찾는 자리수보다 한자리 적은 자릿수까지의 누적 개수

 

의 값을 찾는다고 생각하고 다시 위 과정을 해당 값에 대해 반복한다.

(찾는 수 = 찾는 수를 넘기 직전의 카운트) 를 하면, 그 결과로 i자리수 중 j 로 시작하는 숫자들 중

찾는 수자가 몇번째 숫자인지 정보를 알 수 있다.

 

찾는 자리수보다 한자리 적은 자릿수까지의 누적 개수

 

이 값을 더해주는 이유는, 첫번째 자리 숫자를 찾았으면, 그 다음 자릿수를 찾아야 하니,

그걸 위해 시작점을 맞춰주는 역할이다.

---

위 알고리즘을 구현한 코드이다.

def find(_n):
    count, last_count = 0, 0
    for length in range(1, 11):
        for first in range(10):
            last_count = count
            count += dp[length][first]
            if count >= _n:
                break

        if count >= _n:
            break

    if count < _n: ## 다 셌는데도 카운트가 모자라면 안되는 거
        return -1

    if length == 1:
        return str(first)

    return str(first) + find(row_count[length-2] + (_n - last_count))


n = int(input())
dp = [[0 for _ in range(10)] for _ in range(11)]
row_count = [0]
for i in range(10):
    dp[1][i] = 1
row_count.append(sum(dp[1]))

for i in range(2, 11):
    for j in range(1, 10):
        dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
    row_count.append(row_count[-1] + sum(dp[i]))

print(find(n+1))

# 테스트로 모든 수를 출력해봤다. (애초에 이게 가능한 시점에서 브루트포스를 의심했어야 했다.)
#for i in range(1, 1024):
#    print(i, find(i))

 

정말 쓸데없이 복잡한 알고리즘인데, 차라리 이걸 더 간단하게 하면

함수를 i 번째 자리인 숫자중에서 j 번째 숫자를 찾도록 하는게 더 나았을 것 같다.

(첫자리부터 마지막 자리 숫자까지 하나씩 찾는 과정에서, DP테이블을 중복으로 방문하기 때문이다.)

 

def find(length, _n):
    count, last_count = 0, 0
    for first in range(10):
        last_count = count
        count += dp[length][first]
        if count >= _n:
            break

    if length == 1:
        return str(first)

    return str(first) + find(length - 1, _n - last_count)


n = int(input())
dp = [[0 for _ in range(10)] for _ in range(11)]
row_count = [0]
for i in range(10):
    dp[1][i] = 1
row_count.append(sum(dp[1]))

for i in range(2, 11):
    for j in range(1, 10):
        dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
    row_count.append(row_count[-1] + sum(dp[i]))

for i in range(1, 11):
    if n+1 <= row_count[i]:
        print(find(i, n+1 - row_count[i-1]))
        exit()

print(-1)

 

아까 코드를 조금 수정했다.

이걸로 i 번째 자릿수를 구할 땐 해당 자리수의 dp 열만 체크하도록 하여 시간을 좀 더 줄여보았다.

 

 

8ms를 더 줄일 수 있었다.

같은 코드를 pypy로 제출해보니 오히려 오래걸렸다.

---

백트래킹 아이디어로 한번 풀어보려고 했는데, 재귀로 구현하다보니까 숫자 순서대로 방문하는게 안되는 문제가 있었다.

0 -> 1 -> 10 -> 2 -> 20 -> 21 -> 3 ->  이런식으로 방문하는 것이었다.

 

그런데 이걸 보다보니 이건 DFS와 BFS의 차이와 똑같았다.

그래서 그냥 BFS로 구현했다.

 

from collections import deque
d = deque()
count = -1
n = int(input())
for i in range(10):
    d.append(i)
while d:
    now_num = d.popleft()
    count += 1

    if count == n:
        print(now_num)
        exit()

    for i in range(now_num%10):
        d.append(now_num*10 + i)

print(-1)

 

매우 직관적이고 엄청 간단해졌다.

 

근데 백트래킹으로 푸는건 정말 안떠오른다...

아무래도 다시 기초 알고리즘을 복습해야 할 것 같다...