🥨 백준 17086. 아기 상어 2

문제

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자.

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

예제 입력 1

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

예제 출력 1

2

예제 입력 2

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1

예제 출력 2

2

알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색

코드

from collections import deque

n, m = map(int, input().split())
arr = []

shark = deque() # 상어 위치 좌표
for i in range(n):
    temp = list(map(int, input().split()))
    for t in range(m):
        if temp[t] == 1: # 해당 좌표에 상어가 있다면
            shark.append((i,t)) # 큐에 좌표를 저장
    arr.append(temp)

mx = [-1, -1, -1, 0, 1, 0, 1, 1] # 대각선 방향까지 합쳐 총 8개
my = [-1, 0, 1, 1, 1, -1, 0, -1]


def bfs():
    while shark: # 상어가 있는 좌표를 돈다.
        x, y = shark.popleft() # x,y 는 상어가 있는 좌표이다.
        for k in range(8):
            dx = x + mx[k] # 이동 x 좌표
            dy = y + my[k] # 이동 y 좌표
            if 0 <= dx < n and 0 <= dy < m: # 이동 좌표가 공간크기 내에 있고
                if arr[dx][dy] == 0: # 해당 칸에 상어가 없다면
                    shark.append((dx,dy)) # 큐에 좌표 저장
                    arr[dx][dy] = arr[x][y] + 1 # 이동 좌표의 값 = 원래 좌표 +1
    return


bfs()
safe_dist = 0
# 전체 좌표를 돌며 탐색
for i in range(n):
    for j in range(m):
        safe_dist = max(safe_dist, arr[i][j]) # 최댓값 탐색

print(safe_dist - 1) # 원래 좌표값의 1은 빼준다.

---

🥨 백준 14651. 걷다보니 신척역 삼

문제

욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 걷다보니 신천역 삼, 그리고 특히 일이삼을 좋아한다. 그래서 욱제는 3을 가지고 놀아보기로 했삼.

3개 숫자(0, 1, 2)만 가지고 N자리 3의 배수를 만들어 보삼. 만드는 배수는 자연수 이삼. 0으로 시작하는 수는 만들 수 없는 수 이삼. 3의 배수가 몇 개나 나올 수 있삼?

입력

N을 입력 받으삼 (1 ≤ N ≤ 33,333)

출력

0, 1, 2만 가지고 만들 수 있는 N자리 3의 배수의 개수를 출력하삼. 숫자가 너무 커질 수 있으니까 답을 109+9(1,000,000,009)로 나눈 나머지를 출력하삼.

예제 입력 1

1

예제 출력 1

0

예제 입력 2

3

예제 출력 2

6

예제 입력 3

10

예제 출력 3

13122

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 정수론

풀이

• n = 1 -> 0
• n = 2 -> 2
• n = 3 -> 6
• n = 4 -> 18
• n = 5 -> 54

코드

N = int(input())
dp = [0 for _ in range(N+1)] # dp 생성

if N >= 2: # 1자리수로는 3의 배수 생성 불가
    dp[2] = 2 # 2자리수로 만들 수 있는 3의 배수: 12, 21
    for i in range(3, N+1): # 이후 자리수부터는 이전수의 3배가 된다는 점을 이용
        dp[i] = (dp[i-1] * 3) % 1000000009 # 매 자리수 마다 3씩 곱하는 점화식 작성

print(dp[N])

---

🥨 백준 2011. 암호코드

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
상근: 얼마나 많은데?
선영: 구해보자!
어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

예제 입력 1

25114

예제 출력 1

6

예제 입력 2

1111111111

예제 출력 2

89

알고리즘 분류

다이나믹 프로그래밍

코드

n = list(map(int,input()))
l = len(n)
dp = [0 for _ in range(l+1)]

if (n[0] == 0) : # n이 0일때
    print("0")
else :
    n = [0] + n # n 리스트 맨앞에 [0]추가 -> dp 배열 1부터 시작하기 때문
    dp[0]=dp[1]=1
    for i in range(2, l+1): # n의 암호를 차례로 순차 탐색
        if n[i] > 0:
            dp[i] += dp[i-1] # 이전까지의 dp 더함
        temp = n[i-1] * 10 + n[i] # temp는 두자리 수의 숫자를 의미한다.
        if temp >= 10 and temp <= 26 : # temp가 암호 범위 내의 두자리 수라면
            dp[i] += dp[i-2] # 전전까지의 dp 더함
    print(dp[l] % 1000000)

---

🥨 프로그래머스 - 마법의 엘리베이터

문제 설명

마법의 세계에 사는 민수는 아주 높은 탑에 살고 있습니다. 탑이 너무 높아서 걸어 다니기 힘든 민수는 마법의 엘리베이터를 만들었습니다. 마법의 엘리베이터의 버튼은 특별합니다. 마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10c (c ≥ 0 인 정수) 형태인 정수들이 적힌 버튼이 있습니다. 마법의 엘리베이터의 버튼을 누르면 현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동하게 됩니다. 단, 엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않습니다. 민수의 세계에서는 0층이 가장 아래층이며 엘리베이터는 현재 민수가 있는 층에 있습니다.

마법의 엘리베이터를 움직이기 위해서 버튼 한 번당 마법의 돌 한 개를 사용하게 됩니다.예를 들어, 16층에 있는 민수가 0층으로 가려면 -1이 적힌 버튼을 6번, -10이 적힌 버튼을 1번 눌러 마법의 돌 7개를 소모하여 0층으로 갈 수 있습니다. 하지만, +1이 적힌 버튼을 4번, -10이 적힌 버튼 2번을 누르면 마법의 돌 6개를 소모하여 0층으로 갈 수 있습니다.

마법의 돌을 아끼기 위해 민수는 항상 최소한의 버튼을 눌러서 이동하려고 합니다. 민수가 어떤 층에서 엘리베이터를 타고 0층으로 내려가는데 필요한 마법의 돌의 최소 개수를 알고 싶습니다. 민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey 가 주어졌을 때, 0층으로 가기 위해 필요한 마법의 돌의 최소값을 return 하도록 solution 함수를 완성하세요.

제한사항

1 ≤ storey ≤ 100,000,000

입출력 예

storey result
16 6
2554 16

코드

def solution(storey):
    answer = 0

    while storey: # storey 값이 존재하는 동안 계속 반복
        remainder = storey % 10 # 10씩 나눈 나머지를 저장 
        if remainder > 5: # 6 ~ 9
            answer += (10 - remainder)
            storey += 10 # 6~9 사이면 남은 값은 더한 후 10승만큼씩 내려가는게 빠르다.
        elif remainder < 5: # 0 ~ 4
            answer += remainder # 0~4 사이면 갯수만큼 내려가는게 빠르다.
        else: # 5
            if (storey // 10) % 10 > 4: # 윗자리수가 5이상일 때
                storey += 10 # 윗 자리수에 1을 더해주어 그 다음 케이스에서 남은 값을 빼주는게 더 빠르다.
            answer += remainder
        storey //= 10 # 다음 자리수 계산

    return answer