D - Lunlun Number

ABC161のD問題。

• https://atcoder.jp/contests/abc161/tasks/abc161_d

各ルンルン数の組み合わせについてqueueを使って回していく感じになる。 bfsまでは行かないけど、bfsチックな解き方を覚えているとできるタイプの問題かな。

from collections import deque


def solve():

    K = int(input())

    dq = deque()
    # 一桁のケース
    for i in range(9):
        dq.append(i+1)

    for i in range(K):
        num = dq.popleft()
        if num % 10 != 0:
            dq.append(num*10+num % 10-1)
        dq.append(num*10+num % 10)
        if num % 10 != 9:
            dq.append(num*10+num % 10+1)

    print(num)


if __name__ == "__main__":  
    solve()