◾ 망가진 계산기 : 백준 1443번
문제
다솜이의 보물 1호는 계산기이다. 어느 날 계산기를 떨어뜨리게 되었고, 계산기가 망가지게 되었다. 계산기는 이제 D자리까지 밖에 나타나지 않는다. 다솜이는 이 계산기를 이용해서 재미있는 일을 해보려고 한다.
가장 처음에 계산기에 표시되어 있는 수는 1이다. 다솜이는 계산기에서 정확하게 P번 만큼의 곱셈을 하려고 한다. 한번의 곱셈에 다솜이는 화면에 나와있는 수에 2와 9를 포함해서 그 사이에 있는 자연수를 곱하려고 한다. 수를 곱한 결과는 반드시 D자리 이하여야 한다. 다솜이가 P번의 곱셈을 해서 구할 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에 다솜이의 계산기가 표시할 수 있는 자리수 D와 다솜이가 하려고하는 연산의 수 P가 주어진다.
- D는 2보다 크거나 같고, 8보다 작거나 같은 자연수
- P는 30보다 작거나 같은 음이아닌 정수
출력
- 첫째 줄에 다솜이가 만들 수 있는 가장 큰 수를 출력한다.
- 만약 P번의 연산을 수행했을 때 나오는 결과가 모두 D자리를 넘어간다면 -1을 출력한다.
입출력 예
| Input | Output |
|---|---|
| 4 3 | 729 |
| 8 0 | 1 |
| 2 3 | 98 |
| 8 10 | 99574272 |
| 8 20 | 99532800 |
| 8 30 | -1 |
| 2 6 | 96 |
| 3 1 | 9 |
◾ 풀이
1. 해설
- 가능한 모든 경우를 탐색하며 최대값을 찾는다.
- 같은 횟수로 계산한 값을 체크하며 방문하지 않은 경우만 체크한다.
- 가능한 자리수를 넘어서지 않는 경우만 체크한다.
2. 프로그램
- d, p 입력
- visit_nums, result 초기화
max_value: 가능한 최대값 계산- 앞서 방문한 결과이거나 가능한 자리수(d)를 넘어서는 경우 : 종료
- 가능한 경우
- (계산 횟수, 현재값) 방문 표시
- 계산 횟수와 p가 같을 경우 : 최대값으로 변경, 종료
- 2 ~ 9 사이의 값을 곱하며 계산
# 코드
# 현재 값 자리수 계산
def length(value):
cnt = 0
while value > 0:
cnt += 1
value //= 10
return cnt
# 최대값 계산
def max_value(d, cnt, value):
# 앞서 나온 결과이거나 d 자리수를 넘어서는 경우 종료
if (cnt, value) in visit_nums or length(value) > d:
return
# 현재 값 방문 표시 (계산 횟수, 값)
visit_nums[(cnt, value)] = True
# p 횟수 만큼 계산한 경우 최대값 결정
if cnt == p:
global result
# 최대값으로 변경
result = max(result, value)
return
# 2 ~ 9 사이의 값을 곱하여 확인
for v in range(2, 10):
max_value(d, cnt+1, value * v)
# d, p 입력
d, p = map(int, input().split())
visit_nums = {} # 방문 표시 dict
result = -1 # 결과 저장 변수
# p가 0인 경우 기본값으로 설정
if p == 0:
result = 1
# p가 1인 경우 9가 최대값
elif p == 1:
result = 9
# 만들 수 있는 최소값의 자리수가 d를 넘는 경우 -1로 설정
elif length(2 ** p) > d:
result = -1
else:
max_value(d, 0, 1)
print(result)
후라이드 치킨