백준 31110번: Autobiography [Python]

작성일 2026-03-02 | In 백준

골드 III

더 읽어보기 »

백준 32984번: 겨울이 좋아 [Python]

작성일 2026-02-12 | In 백준

골드 III

더 읽어보기 »

백준 2842번: 집배원 한상덕 [C++]

작성일 2026-02-11 | In 백준

플래티넘 IV

더 읽어보기 »

백준 14595번: 동방 프로젝트 (Large) [Python]

작성일 2026-01-03 | In 백준

골드 IV

더 읽어보기 »

백준 12099번: 점심메뉴 [Python]

작성일 2025-11-07 | In 백준

골드 IV

더 읽어보기 »

랜덤 마라톤 · 코스 72

작성일 2025-10-15 | In 랜덤 마라톤

A. 공약수

브론즈 II

유클리드 호제법으로 공약수를 구한 뒤 약수를 출력하면 됩니다.

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b

    return a


def main():
    n = int(input())
    g = 0

    for i in map(int, input().split()):
        g = gcd(g, i)

    for d in range(1, g + 1):
        if g % d == 0:
            print(d)


main()

B. 디지털시계

브론즈 I

문제에서 요구하는 것을 잘 구현하면 됩니다.

class Time:
    def __init__(self, time: str):
        self.h, self.m, self.s = map(int, time.split(":"))

    def add(self, sec: int):
        self.s += sec

        if self.s >= 60:
            self.m += self.s // 60
            self.s %= 60

        if self.m >= 60:
            self.h += self.m // 60
            self.m %= 60

        if self.h >= 24:
            self.h %= 24

    def __ne__(self, other: object) -> bool:
        if isinstance(other, Time):
            return self.h != other.h or self.m != other.m or self.s != other.s
        return True

    def __eq__(self, other: object) -> bool:
        return not self != other

    def isMultipleOf(self, num: int) -> bool:
        return (self.h * 10000 + self.m * 100 + self.s) % num == 0


def main():
    for _ in range(3):
        cnt = 0

        start, end = map(Time, input().split())
        end.add(1)

        if start == end:
            if start.isMultipleOf(3):
                cnt += 1
            start.add(1)

        while start != end:
            if start.isMultipleOf(3):
                cnt += 1

            start.add(1)

        print(cnt)


main()

C. 줄자접기

실버 III

줄자의 길이를 $l$이라 하고 수직선 위의 두 점 $0$과 $l - 1$을 잇는 선분으로 생각해 봅시다.

점 $m$을 기준으로 반으로 접으면 줄자의 길이는 $\max(m, l - m)$이 됩니다.

접는 점을 원점인 $0$으로 재조정하면 $m$보다 왼쪽에 있는 점 $x$는 $m - x$, 오른쪽에 있는 점 $y$는 $y - m$으로 바꿀 수 있습니다.

def main():
    length = float(input())
    red = sorted(map(float, input().split()))
    blue = sorted(map(float, input().split()))
    yellow = sorted(map(float, input().split()))

    m = (red[0] + red[1]) / 2
    length = max(m, length - m)

    blue = sorted(map(lambda x: abs(x - m), blue))
    yellow = sorted(map(lambda x: abs(x - m), yellow))

    if blue[0] != blue[1]:
        m = (blue[0] + blue[1]) / 2

        yellow = sorted(map(lambda x: abs(x - m), yellow))
        length = max(m, length - m)

    if yellow[0] != yellow[1]:
        m = (yellow[0] + yellow[1]) / 2
        length = max(m, length - m)

    print(f"{length:.1f}")


main()

D. 아이템 배치하기

실버 II

강화력이 큰 것부터 내림차순으로 배치하는것이 이득입니다.

현재까지 강화된 아이템의 최대 인덱스를 관리하는 방법으로 $\mathcal{O}(N)$에 해결할 수 있습니다.

강화력이 $0$이면 break하도록 하면 현재까지 봤던 아이템들은 모두 강화된 상태이므로 강화된 아이템의 최대 인덱스가 $N$이 넘어가면 $N$개가 모두 강화됨을 알 수 있습니다.

def main():
    N = int(input())
    A = sorted(map(int, input().split()), reverse=True)

    r = -1

    for i in range(N):
        if A[i] == 0:
            break

        r = min(max(r, i + A[i] - 1), N - 1)

    print(r + 1)


main()

E. 이미지 축소

실버 I

연속으로 열이 같은 모든 경우의 최대 공약수, 행이 같은 모든 경우의 최대 공약수를 각각 구하면 가장 큰 $i, j$를 구할 수 있습니다.

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a


def main():
    ni, mj = map(int, input().split())

    image = [list(input()) for _ in range(ni)]

    j = 0
    consecutive = 1
    for c in range(1, mj):
        isSame = True
        for r in range(ni):
            if image[r][c] != image[r][c - 1]:
                isSame = False

        if isSame:
            consecutive += 1
        else:
            j = gcd(j, consecutive)
            consecutive = 1

    j = gcd(j, consecutive)

    i = 0
    consecutive = 1
    for r in range(1, ni):
        isSame = True
        for c in range(0, mj, j):
            if image[r][c] != image[r - 1][c]:
                isSame = False

        if isSame:
            consecutive += 1
        else:
            i = gcd(i, consecutive)
            consecutive = 1

    i = gcd(i, consecutive)

    print(ni // i, mj // j)
    for r in range(0, ni, i):
        for c in range(0, mj, j):
            print(image[r][c], end="")
        print()


main()

F. 가희와 무궁화호

골드 V

그냥 열심히 구현하면 됩니다…

다음 날로 넘어가는 부분을 구현할 때 주의합시다.

from typing import cast


class Time:
    def __init__(self, h: int, m: int):
        self.h = h
        self.m = m

    @staticmethod
    def parseTime(time: str) -> "Time":
        if time == "-:-":
            return Time(0, 0)
        return Time(*map(int, time.split(":")))

    def __int__(self) -> int:
        return self.h * 60 + self.m

    def __str__(self) -> str:
        return f"{self.h:0>2}:{self.m:0>2}"

    def __add__(self, other: "int | Time") -> "Time":
        m = int(self) + int(other)

        isNegative = m < 0
        m = abs(m)

        h = m // 60
        m %= 60

        return Time(-h, -m) if isNegative else Time(h, m)

    def __sub__(self, other: "Time") -> "Time":
        return self + (-int(other))

    def getDuration(self, to: "Time") -> "Time":
        t = to - self

        if int(t) < 0:
            t += Time(24, 0)

        return t


dist = {
    "Seoul": 0,
    "Yeongdeungpo": 9.1,
    "Anyang": 23.9,
    "Suwon": 41.5,
    "Osan": 56.5,
    "Seojeongri": 66.5,
    "Pyeongtaek": 75.0,
    "Seonghwan": 84.4,
    "Cheonan": 96.6,
    "Sojeongni": 107.4,
    "Jeonui": 114.9,
    "Jochiwon": 129.3,
    "Bugang": 139.8,
    "Sintanjin": 151.9,
    "Daejeon": 166.3,
    "Okcheon": 182.5,
    "Iwon": 190.8,
    "Jitan": 196.4,
    "Simcheon": 200.8,
    "Gakgye": 204.6,
    "Yeongdong": 211.6,
    "Hwanggan": 226.2,
    "Chupungnyeong": 234.7,
    "Gimcheon": 253.8,
    "Gumi": 276.7,
    "Sagok": 281.3,
    "Yangmok": 289.5,
    "Waegwan": 296.0,
    "Sindong": 305.9,
    "Daegu": 323.1,
    "Dongdaegu": 326.3,
    "Gyeongsan": 338.6,
    "Namseonghyeon": 353.1,
    "Cheongdo": 361.8,
    "Sangdong": 372.2,
    "Miryang": 381.6,
    "Samnangjin": 394.1,
    "Wondong": 403.2,
    "Mulgeum": 412.4,
    "Hwamyeong": 421.8,
    "Gupo": 425.2,
    "Sasang": 430.3,
    "Busan": 441.7,
}


def main():
    N, Q = map(int, input().split())

    arrival: dict[str, Time] = {}
    departure: dict[str, Time] = {}

    for _ in range(N):
        name, arr, dep = input().split()

        arrival[name] = Time.parseTime(arr)
        departure[name] = Time.parseTime(dep)

    for _ in range(Q):
        start, end = input().split()

        t = departure[start].getDuration(arrival[end])

        print(abs(dist[end] - dist[start]) / int(t) * 60)


main()

G. 용액 합성하기

골드 V

두 포인터로 $\mathcal{O}(N)$에 해결할 수 있습니다.

$l = 0$, $r = N - 1$로 초기화합시다.

$A_l + A_r < 0$인 경우 합을 늘려야 하므로 $l$을 증가시킵니다.

$A_l + A_r > 0$인 경우 합을 줄여야 하므로 $r$을 감소시킵니다.

def main():
    N = int(input())
    A = list(map(int, input().split()))

    l = 0
    r = N - 1

    ans = A[0] + A[1]

    while l < r:
        if abs(A[l] + A[r]) < abs(ans):
            ans = A[l] + A[r]

        if A[l] + A[r] < 0:
            l += 1
        else:
            r -= 1

    print(ans)


main()

번외로, 이분 탐색으로도 해결할 수 있습니다.

def upper_bound(arr: list, target) -> int:
    lo = 0
    hi = len(arr)

    while lo < hi:
        m = (lo + hi) >> 1

        if arr[m] <= target:
            lo = m + 1
        else:
            hi = m

    return lo


def main():
    N = int(input())
    A = list(map(int, input().split()))

    if 0 in A:
        if A.count(0) >= 2:
            print(0)
            return

    ans = A[0] + A[1]

    for i in range(N):
        if A[i] == 0:
            continue

        j = upper_bound(A, -A[i])

        if 0 <= j - 1 and j - 1 != i and abs(A[i] + A[j - 1]) < abs(ans):
            ans = A[i] + A[j - 1]
        if j < N and j != i and abs(A[i] + A[j]) < abs(ans):
            ans = A[i] + A[j]

    print(ans)


main()

H. 배열 돌리기 2

골드 V

$(i, j)$에 있는 수를 $(i, j + c)$로 옮기고 나머지를 왼쪽으로 한칸씩 당기는 방법을 생각해 봅시다.

$(i, j)$와 $(i, j + 1)$를 교환하고, $(i, j + 1)$와 $(i, j + 2)$를 교환하고… 를 반복하면 됩니다.

따라서 반시계방향으로 회전하는 것은 시계방향으로 교환하는 행위와 같습니다.

회전해야 할 길이로 $R$을 나눈 나머지만큼 회전하면 시간 복잡도 $\mathcal{O}(N^3)$ 정도에 해결할 수 있습니다.

def main():
    N, M, R = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    def rotate(start: tuple[int, int], end: tuple[int, int], dr: int, dc: int):
        r, c = start
        while (r, c) != end:
            nr = r + dr
            nc = c + dc

            A[r][c], A[nr][nc] = A[nr][nc], A[r][c]

            r, c = nr, nc

    r, c = 0, 0
    while r < N - 1 - r and c < M - 1 - c:
        cnt = R % (2 * (N - 2 * r) + 2 * (M - 2 * c) - 4)

        for _ in range(cnt):
            rotate((r, c), (r, M - 1 - c), 0, 1)
            rotate((r, M - 1 - c), (N - 1 - r, M - 1 - c), 1, 0)
            rotate((N - 1 - r, M - 1 - c), (N - 1 - r, c), 0, -1)
            rotate((N - 1 - r, c), (r + 1, c), -1, 0)

        r += 1
        c += 1

    for row in A:
        print(*row)


main()

더 읽어보기 »

랜덤 마라톤 · 코스 71

작성일 2025-10-12 | In 랜덤 마라톤

A. 아이그루스와 화장실

브론즈 III

안뇽이는 $K$가 홀수이면 $K$층, 짝수이면 $K - 1$층으로 가면 됩니다.

인덕이는 $K$가 짝수이면 $K$층, $K = 1$이면 $2$층, 아니면 $K - 1$층으로 가면 됩니다.

def solve():
    N = int(input())
    mascot = input()
    K = int(input())

    ans = 0
    if mascot == "annyong":
        if K & 1:
            ans = K
        else:
            ans = K - 1
    else:
        if ~K & 1:
            ans = K
        elif K == 1:
            ans = 2
        else:
            ans = K - 1

    print(ans)


solve()

B. 중복된 숫자

실버 V

$1$부터 $N - 1$까지의 합에 $A$의 원소를 모두 빼면 중복되는 수와 부호가 반대인 수가 됨을 알 수 있습니다.

파이썬에서 정수들을 한 줄에 한번에 입력받으면 메모리 초과를 받으므로 sys.stdin.read를 이용해서 정수를 하나씩 읽어 메모리를 절약했습니다.

import sys

def read_int():
    ret = 0
    c = sys.stdin.read(1)
    while not c.isspace():
        ret *= 10
        ret += ord(c) - ord("0")
        c = sys.stdin.read(1)

    return ret


N = read_int()

total = N * (N - 1) // 2

for i in range(N):
    total -= read_int()

print(-total)

C. The primes contain arbitrarily long arithmetic progressions

실버 V

초항이 $2$고 공차가 $0$인 등차수열을 출력하면 됩니다.

n = int(input())
print("2 " * n)

D. 어두운 굴다리

실버 IV

가로등의 높이는 최소 $\max(x_1, N - x_M)$이어야 합니다.

임의의 두 가로등 사이에 비춰지지 않는 곳이 존재하면 안 되므로 $i = 1$부터 $N - 1$까지 $i$번째 가로등과 $i + 1$번째 가로등 사이가 모두 비춰질 때 까지 가로등을 높여줍시다.

가로등의 높이가 $N$이 되면 모두 비출 수 있으므로 가로등의 높이는 최대 $N$번 증가하고 따라서 시간 복잡도 $\mathcal{O}(N)$에 해결할 수 있습니다.

def solve():
    N = int(input())
    M = int(input())
    x = list(map(int, input().split()))

    height = x[0]
    lightBound = x[0] + height
    for i in range(1, M):
        while lightBound < x[i] - height:
            height += 1
            lightBound += 1
        lightBound = x[i] + height

    if x[-1] + height < N:
        height = N - x[-1]

    print(height)


solve()

E. 서바이벌

실버 III

선분들이 단순다각형을 이루려면 $s_{i + 1}$번 학생이 $s_i$번 학생에게 총을 쏘면 안 되므로 $s_i$와 $s_{i + 1}$ 사이의 거리보다 $s_{i + 1}$과 $s_{i + 2}$ 사이의 거리가 더 짧거나 같아야 합니다.

그렇다면 $s_1$와 $s_2$ 사이의 거리보다 $s_M$과 $s_1$ 사이의 거리가 더 짧거나 같아야 합니다. 만약 더 짧다면 $s_1$번 학생이 $s_2$번 학생에게 총을 쏘았다는 것에 모순되므로 모든 선분의 길이는 같아야 합니다.

그러나 거리가 같은 경우 번호가 큰 학생에게 총을 쏘아야 하므로 번호가 단조 증가/감소해야 합니다. 이때 규칙에 따라 $s_i$가 최대인 학생에게 총을 쏘는 학생이 정확하게 두 명 존재해야 하고, $s_i$가 최대인 학생은 그 두 학생 중 하나에게 총을 쏘아야 하므로 선분이 겹치게 되고 이는 각 총알의 경로가 양 끝점 이외의 다른 점에서 다른 경로와 만나지 않는다는 것과 모순입니다.

따라서 단순다각형을 이루도록 하는 입력은 존재하지 않습니다.

print(-1)

F. 도어맨

실버 II

남자와 여자의 수 차이가 줄어든다면 두 번째 사람을 먼저 입장시키는 것이 이득이고, 그렇지 않으면 어떤 사람을 먼저 입장시키든 상관 없습니다.

WOMAN = 0
MAN = 1


def charToGender(c: str):
    if c == "W":
        return WOMAN
    else:
        return MAN


def solve():
    X = int(input())
    line = list(map(charToGender, input()))

    count = [0, 0]

    i = 0
    while i < len(line):
        now = line[i]
        i += 1

        while i < len(line) and count[line[i]] < count[line[i] ^ 1]:
            count[line[i]] += 1
            i += 1

        count[now] += 1

        if abs(count[0] - count[1]) > X:
            i -= 1
            break

    print(i)


solve()

G. 레벨 햄버거

골드 V

레벨-$N$ 버거에 들어있는 패티의 개수를 $P_N$이라 하면 $P_N = 2P_{N - 1} + 1$입니다.

레벨-$N$ 버거의 레이어의 수를 $L_N$이라 하면 $L_N = 2L_{N - 1} + 3$입니다.

동적 계획법을 이용해서 $P_N$과 $L_N$을 전처리해 두고 재귀적으로 레이어 개수 $X$이하인 부분의 패티의 개수를 구해주면 됩니다.

def solve():
    N, X = map(int, input().split())

    # preprocesses powers of 2
    pattyCnt = [0] * (N + 1)
    pattyCnt[0] = 1
    for i in range(1, N + 1):
        pattyCnt[i] = pattyCnt[i - 1] << 1 | 1

    layerOfLv = [0] * (N + 1)
    layerOfLv[0] = 1
    for i in range(1, N + 1):
        layerOfLv[i] = (layerOfLv[i - 1] << 1) + 3

    def getPattyCnt(level: int, layer: int) -> int:
        if layer <= 0:
            return 0
        if level == 0:
            return 1

        ret = 0

        layer -= 1

        if layer >= layerOfLv[level - 1]:
            ret += pattyCnt[level - 1]
            layer -= layerOfLv[level - 1]
        else:
            return ret + getPattyCnt(level - 1, layer)

        if layer <= 0:
            return ret

        ret += 1
        layer -= 1

        if layer >= layerOfLv[level - 1]:
            ret += pattyCnt[level - 1]
        else:
            return ret + getPattyCnt(level - 1, layer)

        return ret

    print(getPattyCnt(N, X))


solve()

H. 그리드 게임

골드 V

지문에 오류가 있습니다. 자세한 내용은 게시판 글을 참조해 주세요.

너비 우선 탐색으로 탐색한 곳의 개수를 세면 됩니다.

from collections import deque


def solve():
    N, M = map(int, input().split())

    queue: deque[tuple[int, int]] = deque()

    for i in range(N):
        line = input()
        for j in range(M):
            if line[j] == "o":
                queue.append((i, j))

    K = int(input())
    time = [[-1] * (M + 2 * K) for _ in range(N + 2 * K)]

    for i, j in queue:
        time[i][j] = 0

    ans = 0
    while queue:
        i, j = queue.popleft()
        ans += 1

        if time[i][j] == K:
            continue

        delta = [1, -1, 0, 0]
        for k in range(4):
            ni = i + delta[k]
            nj = j + delta[3 - k]

            if time[ni][nj] != -1:
                continue

            time[ni][nj] = time[i][j] + 1
            queue.append((ni, nj))

    print(ans)


solve()