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

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)

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

이 문제는 단순한 그래프 탐색이다.

하나 다른 문제들과 다른 점이 있다면, 아마 처음에 직사각형들을 색칠한다는 것?

그 후에는 그냥 단순히 넓이를 하나씩 입력해주고 그거를 그대로 출력해주면 끝난다.

from collections import deque
import sys
import heapq

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

result_list = list()

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

paper = [[0 for _ in range(M)] for _ in range(N)]

for _ in range(K):
    start_x, start_y, end_x, end_y = map(int, sys.stdin.readline().split())

    for x in range(start_x, end_x):
        for y in range(start_y, end_y):
            paper[x][y] = 1

for x in range(N):
    for y in range(M):
        if paper[x][y] == 0:
            need_visit = deque()

            paper[x][y] = -1
            need_visit.append([x, y])

            result = 0

            while need_visit:

                cur_x, cur_y = need_visit.popleft()

                result += 1

                for i in range(4):
                    next_x, next_y = cur_x + dx[i], cur_y + dy[i]
                    if 0 <= next_x < N and 0 <= next_y < M and paper[next_x][next_y] == 0:
                        paper[next_x][next_y] = -1
                        need_visit.append([next_x, next_y])

            heapq.heappush(result_list, result)

print(len(result_list))

while result_list:
    print(heapq.heappop(result_list), end=' ')

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

BFS, DFS의 문제는 아니고 find와 union을 사용해서 해결하는 문제이다.

find 함수

def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]

해당 그래프에서 최상위 노드를 구해주는 함수이다.

만약 find로 구한 노드가 같으면, 같은 그래프에 속하는 노드인 것이다.

union 함수이다.

같은 그래프에 속하지 않는 노드들을 연결해주는 함수이다.

def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1

이 함수들을 이용해서 같은 그래프에 속하는 노드끼리 묶어주고, 마지막에 여행을 가려는 노드들이 같은 그래프에 있는 지 확인을 해주면 된다.

import sys

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

parent = [i for i in range(N)]
rank = [0 for _ in range(N)]

city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

trip = []

if M > 0:
    trip = list(map(int, sys.stdin.readline().split()))


def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]


def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1


for i in range(N):
    for t in range(i):
        if city[i][t] == 1:
            if find(i) != find(t):
                union(i, t)

standard = find(trip[0] - 1)
flag = True

for i in range(1, M):
    if standard != find(trip[i] - 1):
        flag = False

print('YES' if flag else 'NO')

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

원래 푸는 방법대로 풀지 않은 거 같다.

원래는 1번 노드에서 가장 먼 곳을 찾은 후, 그 노드에서 가장 먼 곳과의 거리를 구하면 된다.

그러면 노드에서는 지름을 구할 수 있다.

하지만 그냥 아무생각없이 모든 노드를 방문하는 방법으로 풀었는데, 그냥 풀렸다.

그래서 이번 문제는 그냥 간단하게 푸는 방법으로 풀도록 하겠다.

이번에는 그래프를 dict로 받았는데, 모든 노드에 대한 2차원 배열로 만들면 메모리 초과가 발생한다.

그냥 반복마다, 최대의 길이를 구하고 그 중에서 최대의 길이를 출력한다.

import sys
from collections import deque

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

node = {i: [] for i in range(n)}

for i in range(n - 1):
    start, end, weight = map(int, sys.stdin.readline().split())

    node[start - 1].append([end - 1, weight])
    node[end - 1].append([start - 1, weight])

result = 0

for i in range(n):
    cur_result = 0
    visited = [False for _ in range(n)]
    need_visit = deque()
    need_visit.append([0, i])
    visited[i] = True

    while need_visit:

        cur_weight, cur_node = need_visit.popleft()

        cur_result = max(cur_result, cur_weight)

        for next_node, next_weight in node[cur_node]:
            if visited[next_node] is False:
                visited[next_node] = True
                need_visit.append([cur_weight + next_weight, next_node])

    result = max(result, cur_result)

print(result)

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

평범한 그래프 문제였지만, 이동이 있었는지 체크하며 수를 하나씩 늘리는 과정이 좀 귀찮았다.

한 차례마다 각 칸에 대하여

위, 아래, 좌, 우 이렇게 4방향을 확인하고 만약 차이가 범위 내라면 그래프 탐색을 실행한다.

탐색을 진행하가며 인구수를 더해주고 탐색이 끝나면 총 인구를 칸으로 나누어 인구를 분배한다.

만약 해당 차례에 인구의 이동이 없었다면, 반복문을 종료하고 지금까지 소모한 턴을 출력한다.

import sys
from collections import deque

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

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

nation = list()

for _ in range(N):
    nation.append(list(map(int, sys.stdin.readline().split())))

flag = True

result = 0

while flag:

    flag = False

    visited = [[False for _ in range(N)] for _ in range(N)]

    for r in range(N):
        for c in range(N):
            if visited[r][c] is False:

                visited[r][c] = True

                need_visit = deque()
                change = [[r, c]]

                need_visit.append([r, c])

                people = nation[r][c]

                while need_visit:

                    cur_r, cur_c = need_visit.popleft()

                    for d in range(4):
                        next_r, next_c = cur_r + dx[d], cur_c + dy[d]
                        if 0 <= next_r < N and 0 <= next_c < N and visited[next_r][next_c] is False and L <= abs(nation[cur_r][cur_c] - nation[next_r][next_c]) <= R:
                            change.append([next_r, next_c])
                            visited[next_r][next_c] = True
                            need_visit.append([next_r, next_c])
                            people += nation[next_r][next_c]
                            flag = True

                per_people = people // len(change)

                for next_r, next_c in change:
                    nation[next_r][next_c] = per_people

    if flag:
        result += 1

print(result)

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

백준의 숨바꼭질 문제와 굉장히 비슷하다.

그냥 단순히 배열을 만들어서 BFS로 풀면 끝난다.

import sys
from collections import deque

F, S, G, U, D = map(int, sys.stdin.readline().split())

stair = [float('inf') for _ in range(F + 1)]
stair[S] = 0

need_visit = deque()

need_visit.append(S)

while need_visit:

    cur_stair = need_visit.popleft()

    if cur_stair == G:
        break

    next_up, next_down = cur_stair + U, cur_stair - D

    next_cnt = stair[cur_stair] + 1

    if 0 < next_up <= F and stair[next_up] > next_cnt:
        stair[next_up] = next_cnt
        need_visit.append(next_up)

    if 0 < next_down <= F and stair[next_down] > next_cnt:
        stair[next_down] = next_cnt
        need_visit.append(next_down)


print(stair[G] if stair[G] != float('inf') else "use the stairs")