[백준/Python] 1326. 폴짝폴짝 & 21314. 민겸 수

 

1. 백준 1326. 폴짝폴짝 

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

1326번: 폴짝폴짝

문제

개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.

 

입력

첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리에서 시작하여 b번 징검다리에 가고 싶다는 뜻이다. 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 개구리가 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프하여 갈 수 있는 지를 출력하시오. a에서 b로 갈 수 없는 경우에는 -1을 출력한다. 

import sys
import math
from collections import deque

input = sys.stdin.readline

n = int(input())
nums = [0] + list(map(int, input().split()))
s, e = map(int, input().split())

dp = [math.inf] * (n + 1)
queue = deque()
queue.append(s)
dp[s] = 0

while queue:
    temp = queue.popleft()
    # 왼쪽 순회
    i = 0
    while temp - (nums[temp] * i) > 0:
        dp[temp - (nums[temp] * i)] = min(dp[temp - (nums[temp] * i)], dp[temp] + 1)
        if temp - (nums[temp] * i) == e:
            print(dp[e])
            exit()
        else:
            if temp != temp - (nums[temp] * i):
                queue.append(temp - (nums[temp] * i))
            i += 1
    # 오른쪽 순회
    i = 0
    while temp + (nums[temp] * i) <= n:
        dp[temp + (nums[temp] * i)] = min(dp[temp + (nums[temp] * i)], dp[temp] + 1)
        if temp + (nums[temp] * i) == e:
            print(dp[e])
            exit()
        else:
            if temp != temp - (nums[temp] * i):
                queue.append(temp + (nums[temp] * i))
            i += 1
print(-1)

• 어제 점프점프를 배워서 비슷한 방식으로 접근했다.
• exit() 처음 코드에서 써본 것 같다.
• 이게 효율적인 문제 풀이 방법인지는 잘 모르겠다...
• 77%에서 계속 틀려서 고민했는데 -1 처리를 하지 않아서 그런 거였다 ;_;

 

---

 

2. 백준 21314. 민겸 수 

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

21314번: 민겸 수

문제

민겸이는 로마 숫자를 보고 굉장히 흥미롭다고 생각했다. 그래서 민겸이는 새로운 수 체계인 민겸 수를 창조했다.

민겸 숫자는 0 이상의 정수 N에 대해 10N 또는 5 × 10N 꼴의 십진수를 대문자 M과 K로 이루어진 문자열로 표기한다. 10N 꼴의 십진수는 N + 1개의 M으로, 5 × 10N 꼴의 십진수는 N개의 M 뒤에 1개의 K를 이어붙인 문자열로 나타낸다. 즉, 아래 표처럼 나타낼 수 있다.

민겸 수는 한 개 이상의 민겸 숫자를 이어붙여 만든다. 예를 들어, 민겸 수 MKKMMK는 MK, K, MMK의 세 민겸 숫자를 이어붙여 만들 수 있다.

민겸 수를 십진수로 변환할 때는, 1개 이상의 민겸 숫자로 문자열을 분리한 뒤, 각각의 민겸 숫자를 십진수로 변환해서 순서대로 이어붙이면 된다. 민겸 숫자를 십진수로 변환하는 것은 십진수를 민겸 숫자로 변환하는 과정을 거꾸로 하면 된다. 예를 들어, 민겸 수 MKKMMK는 아래 그림과 같이 여러 가지 십진수로 변환할 수 있다.

 

민겸이는 위와 같이 하나의 민겸 수가 다양한 십진수로 변환될 수 있다는 사실을 알았다. 문득 민겸이는 변환될 수 있는 십진수 중 가장 큰 값과 가장 작은 값이 궁금해졌다. 민겸이를 위해 하나의 민겸 수가 십진수로 변환되었을 때 가질 수 있는 최댓값과 최솟값을 구해주자. 

 

입력

민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다.

출력

주어진 민겸 수가 십진수로 변환되었을 때 가질 수 있는 값 중 가장 큰 값과 가장 작은 값을 두 줄로 나누어 출력한다.

 

import sys

input = sys.stdin.readline

num = list(input().rstrip())

stack = []
max_ans = ''
min_ans = ''

for n in num:
    stack.append(n)
    if n == 'K':
        if len(stack) > 1:
            max_ans += '5' + ('0' * (len(stack) - 1))
            min_ans += '1' + ('0' * (len(stack) - 2)) + '5'
        else:
            max_ans += '5'
            min_ans += '5'
        stack = []

if len(stack) > 0:
    max_ans += '1' * (len(stack))
    min_ans += '1' + ('0' * (len(stack) - 1))

print(max_ans)
print(min_ans)

• 이 문제는 문제를 이해하고 최댓값, 최솟값을 구하기 위한 조건을 파악하니 구현은 금방 됐다.
• 그치만 최댓값, 최솟값을 구하기까지의 과정에서 조금 고민이 필요했다!
• 규칙은 현재 K값일 때 쌓은 stack의 결론을 내고 있는데,
  • 최댓값 : 시작이 5일 때 가장 최댓값이므로 K를 포함하여 값을 낸다.
  • 최솟값 : 시작이 1이고 0이 가장 많을 때 최솟값이므로 K를 빼고 값을 내고 K는 5로만 처리한다.
  • stack이 M으로 끝났을 때는, 최댓값은 M을 개별의 1로 여기고 최솟값은 합쳐진 10진수 값으로 여기면 된다.