100년 뒤 개발자 한승규입니다.

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

공유기와 비슷하게 함수를 만들고 하나씩 돌아가면서 확인하도록 만들었다.

import sys

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().split()))

A.sort()

result = 0


def isGood(goal):
    left, right = 0, N - 1

    while left < right:
        if A[left] + A[right] == A[goal]:
            if left == goal:
                left += 1
            elif right == goal:
                right -= 1
            else:
                return True
        elif A[left] + A[right] > A[goal]:
            right -= 1
        elif A[left] + A[right] < A[goal]:
            left += 1


for i in range(N):
    result += 1 if isGood(i) is True else 0

print(result)

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

당연하게 이분 탐색으로 풀었다.

이분탐색을 푸는 루틴이 생긴 것 같다.

우선 함수를 만들고 그 함수를 기준으로 left 쪽으로 갈지, right 쪽으로 갈지 정하는 것이다.

이번 문제의 함수에서 반환하는 값은 공유기의 개수이다.

거리를 기준으로 공유기를 놓아보고, 만약 공유기가 더 필요하다면 거리를 늘리는 것이다.

import sys

N, M = map(int, sys.stdin.readline().split())

house = []

for i in range(N):
    house.append(int(sys.stdin.readline()))

house.sort()


def wifi(length):
    result = 1
    cur = house[0]
    for i in range(1, N):
        if house[i] >= cur + length:
            cur = house[i]
            result += 1

    return result


left = 1
right = house[-1] - house[0]

while left <= right:
    mid = (left + right) // 2
    cnt = wifi(mid)

    if cnt >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)

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

전에 풀었던 나무 자르기와 비슷하다.

당연히 이분탐색으로 바로 풀었고, 결과를 구해주는 함수는 작성했다.

굳이 설명을 더 적지는 않도록 하겠다.

import sys

K, N = map(int, sys.stdin.readline().split())

lan = list()
max_lan = 0

for i in range(K):
    cur_lan = int(sys.stdin.readline().strip())
    lan.append(cur_lan)
    max_lan = max(max_lan, cur_lan)


def cur_lan(length):
    result = 0
    for lan_length in lan:
        result += (lan_length // length)
    return result


left, right = 0, max_lan

while left <= right:
    mid = (left + right) // 2
    mid = max(1, mid)
    lan_count = cur_lan(mid)

    if lan_count >= N:
        left = mid + 1
    else:
        right = mid - 1

print(right)

import sys

N, M = map(int, sys.stdin.readline().split())

tree = list(map(int, sys.stdin.readline().split()))


def cut(height):
    result = 0
    for i in tree:
        result += max(0, i - height)
    return result


left, right = 0, max(tree)

while left <= right:
    mid = (left + right) // 2
    cur_height = cut(mid)

    if cur_height >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)

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

백준 이분 탐색 중에 가장 많이 푼 문제 중 하나일 거 같다.

그냥 Left, Right를 잡고 범위를 좁혀나간 후 푸는 이분탐색 문제이다.

얻을 수 있는 나무의 길이를 구하기 위해 높이에 따라 얻는 나무를 구해주는 함수는 만들어서 사용했다.

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

뻗어 나가는 느낌으로 풀었다.

다양한 길이를 가져야 하기 때문에 함수를 이용해서 풀 수 있도록 하였다.

소수를 판정 할 때, 어차피 계산 한 부분은 안 할 거 같아서 굳이 에라토스테네스의 체를 쓰지는 않았다.

함수를 이용해서, 만약 길이가 N이라면 해당 수를 바로 출력하고 아니라면 뒤에 수를 계속 붙여주는 방법으로 풀었다.

어차피 앞 부분은 이미 소수일 테니까, 해당 수가 소수인지만 판별을 진행했다.

import sys

N = int(sys.stdin.readline().strip())

prime = [2, 3, 5, 7]


def is_prime(number):
    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0:
            return False
    return True


def wow_prime(cur_number):
    if len(str(cur_number)) == N:
        print(cur_number)
    else:
        for t in range(1, 10):
            if t % 2 != 0 and is_prime(cur_number * 10 + t):
                wow_prime(cur_number * 10 + t)


for i in prime:
    wow_prime(i)

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

소수 문제이기 때문에 당연하게 에라토스테네스의 체를 사용해서 소수를 먼저 구한 후 시작하였다.

그 후 입력마다, 해당 수를 반으로 나누고 반으로 나눈 값들에 1부터 더하거나 빼가며 둘 다 소수라면 반복문을 멈추고 출력하도록 했다.

import sys

T = int(sys.stdin.readline().strip())

prime = [True for _ in range(10001)]

for i in range(2, int(10001 ** 0.5) + 1):
    if prime[i]:
        for t in range(i + 1, 10001):
            if t % i == 0:
                prime[t] = False

for _ in range(T):
    n = int(sys.stdin.readline().strip())

    for i in range(n // 2 + 1):
        if prime[n // 2 - i] and prime[n // 2 + i]:
            print(n // 2 - i, n // 2 + i)
            break

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

일단 당연히 소수와 관련된 문제이기에 에라토스테네스의 체를 사용해서 풀었다.

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

그렇게 풀었어도 시간 문제가 발생했었는데, 입력이 있을 때마다 계산을 해서 출력을 했기 때문이었다.

import sys

while True:
    n = int(sys.stdin.readline().strip())

    if n == 0:
        break

    number = [True for i in range(2 * n + 1)]

    for i in range(2, int((2 * n + 1) ** 0.5) + 1):
        if number[i]:
            for t in range(i + 1, 2 * n + 1):
                if t % i == 0:
                    number[t] = False

    print(number[n + 1: 2 * n + 1].count(True))

이렇게 풀었는 데, 시간 문제가 발생해서

입력을 받기 전에 계산을 모두 해두고, 출력만 바로바로 할 수 있도록 하였다,

import sys

number = [True for i in range(123456 * 2 + 1)]

for i in range(2, int((2 * 123456 + 1) ** 0.5) + 1):
    if number[i]:
        for t in range(i + 1, 2 * 123456 + 1):
            if t % i == 0:
                number[t] = False


while True:
    n = int(sys.stdin.readline().strip())

    if n == 0:
        break

    print(number[n + 1: 2 * n + 1].count(True))

이렇게 풀었더니 시간 문제가 발생하지 않았다.

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

별 다른 방법 없다.

그냥 1씩 더해가면서 해당 수를 찾고 출력하는 것이다.

import sys

E, S, M = map(int, sys.stdin.readline().split())

cur_year = 1

while True:
    if (cur_year - E) % 15 == 0 and (cur_year - S) % 28 == 0 and (cur_year - M) % 19 == 0:
        break
    cur_year += 1

print(cur_year)