망가진 계산기

시간 제한2초메모리 제한128 MB

요약
숫자가 1에서 시작해 최대 D자리까지만 표시되는 계산기에서 2부터 9까지의 수를 정확히 P번 곱해 만들 수 있는 가장 큰 값을 구하고, 불가능하면 -1을 출력합니다.
난이도

보통10점 중 5점

유형
백트래킹, 완전 탐색, DFS, 수학
정답자
아직 제출이 없습니다

문제

다솜이가 가장 아끼는 물건은 계산기이다. 어느 날 계산기를 떨어뜨린 뒤로, 이 계산기는 최대 D자리 수까지만 화면에 표시할 수 있게 되었다.

처음 계산기에 표시된 수는 1이다. 다솜이는 이 계산기로 정확히 P번 곱셈을 하려고 한다. 한 번 곱셈할 때마다 현재 화면에 표시된 수에 2 이상 9 이하의 자연수 하나를 곱한다. 각 곱셈 결과는 반드시 D자리 이하의 수여야 한다.

정확히 P번 곱셈한 뒤 다솜이가 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 계산기가 표시할 수 있는 최대 자리수 D와 다솜이가 수행하려는 곱셈 횟수 P가 주어진다.

D는 2 이상 8 이하의 자연수이고, P는 30 이하의 음이 아닌 정수이다.

출력

정확히 P번 곱셈해서 만들 수 있는 가장 큰 수를 첫째 줄에 출력한다. 정확히 P번 곱셈하는 모든 경우에서 결과가 D자리를 초과한다면 -1을 출력한다.

예제8

  1. 예제 1

    입력
    4 3
    
    예상 출력
    729
    
  2. 예제 2

    입력
    8 0
    
    예상 출력
    1
    
  3. 예제 3

    입력
    2 3
    
    예상 출력
    98
    
  4. 예제 4

    입력
    8 10
    
    예상 출력
    99574272
    
  5. 예제 5

    입력
    8 20
    
    예상 출력
    99532800
    
  6. 예제 6

    입력
    8 30
    
    예상 출력
    -1
    
  7. 예제 7

    입력
    2 6
    
    예상 출력
    96
    
  8. 예제 8

    입력
    3 1
    
    예상 출력
    9