우주의 IT 소행성

나의 코드

n, m = map(int, input().split())
data = sorted(list(map(int, input().split())))


def binary(arr, start, end):
    if start > end:
        return end

    mid = (start + end) // 2
    count = 0
    for i in arr:
        if mid < i:
            count += (i - mid)

    if count == m:
        return mid
    elif count < m:
        return binary(arr, start, mid - 1)
    else:
        return binary(arr, mid + 1, end)

print(binary(data, 0, max(data)))

풀이 방법

이분탐색 랜선 자르기 문제와 유사한 문제

나의 코드

k, n = map(int, input().split())
data = [int(input()) for _ in range(k)]
data.sort()

def binary(arr, start, end):
    if start > end:
        return end

    mid = (start + end) // 2
    lines = 0

    for i in data:
        lines += i // mid

    if lines >= n:
        return binary(arr, mid + 1, end)
    else:
        return binary(arr, start, mid - 1)


print(binary(data, 1, data[-1]))

풀이 방법

binary-search 를 응용하여 풀이

나의 코드

from collections import deque

n, m = map(int, input().split())
graph = [list(input()) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
sonic = deque()
water = deque()
count = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == '*':
            water.append((i, j))
            visited[i][j] = True
        elif graph[i][j] == 'S':
            sonic.append((i, j))
            visited[i][j] = True
        elif graph[i][j] == 'X':
            visited[i][j] == True

while sonic:
    for _ in range(len(water)):
        wx, wy = water.popleft()
        for i in range(4):
            nx = wx + dx[i]
            ny = wy + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == '.':
                    water.append((nx, ny))
                    graph[nx][ny] = '*'
                    visited[nx][ny] = True
    count += 1

    for _ in range(len(sonic)):
        sx, sy = sonic.popleft()
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == '.' and not visited[nx][ny]:
                    sonic.append((nx, ny))
                    visited[nx][ny] = True
                elif graph[nx][ny] == 'D':
                    print(count)
                    exit()
print("KAKTUS")

물이 차오르는 것 + 고슴도치가 이동하는 것을 함께 1사이클로 생각하는 bfs 문제.

나의 코드

import sys
from collections import deque
input = sys.stdin.readline

n, l, r = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    tmp = []
    tmp.append((a, b))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    tmp.append((nx, ny))
    return tmp

result = 0
while True:
    visited =[[False] * (n + 1) for _ in range(n + 1)]
    flag = 0
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                visited[i][j] = True
                cur = bfs(i, j)

                if len(cur) > 1:
                    flag = 1
                    people = sum(graph[x][y] for x, y in cur) // len(cur)
                    for x, y in cur:
                        graph[x][y] = people
    if flag == 0:
        break
    result += 1
print(result)

풀이 방법

bfs 후 해당 지역 값 리스트를 저장하여 평균을 냄

평균을 내다가 더이상 상태가 변하지 않는다면 종료