[BOJ][🟡4][백준#24955] 숫자 이어 붙이기

문제 출처

BAEKJOON Online Judge #24955

문제

철수는 수를 이어 붙이는 놀이를 좋아한다. 1과 2를 이어 붙이면 12가 되고, 17과 13을 이어 붙이면 1713이 된다. 100과 1000을 이어 붙이면 1001000이 된다. 1과 2를 이어 붙이되, 순서를 반대로 해서 2와 1을 이어 붙이면, 21이 된다. 같은 두 수를 이어 붙이더라도, 이어 붙이는 순서에 따라서 값이 달라진다는 것을 알 수 있다. 철수가 살고 있는 마을에는 집이 여러 채 있고, 각 집에는 $1$부터 $N$까지 번호가 붙어있다. 두 집 사이에 존재하는 도로를 통해 서로 이동할 수 있다. 총 $N-1$개의 도로가 존재한다. $i$번째 도로는 $a_i$번 집과 $b_i$집을 잇는다. 집과 도로는 트리의 형태를 이룬다. 즉, 어떤 집에서 시작해서 몇 개의 도로를 거쳐 어떤 집이라도 갈 수 있고, 같은 집을 두 번 방문하지 않을 경우 그 경로는 유일하다. 각각의 집의 대문에는 수가 쓰여있다. 철수는 총 $Q$번 수를 이어 붙이는 놀이를 할 것이다. $i$번째 놀이에서는 $x_i$번째 집에서 시작해서, $y_i$번째 집까지 이동하면서, 이동하는 경로 상에 있는 집들의 대문에 쓰여있는 수들을 방문하는 순서대로 이어 붙일 것이다. 만약 $x_i = y_i$라면, $x_i$번째 집의 대문에 쓰인 수가 답이 될 것이다. 철수는 놀이가 끝날 때마다, 자기가 올바르게 수들을 이어 붙였는지 궁금해졌다. 철수를 위해, $i$번째 놀이가 끝났을 때 이어 붙인 수의 값을 구해주자. 단, 수가 너무 커질 수 있으니까, $1\,000\,000\,007$로 나눈 나머지를 출력하도록 하자.

입력

첫 번째 줄에는 집의 개수 $N$과, 철수가 놀이를 할 횟수 $Q$가 주어진다. 두 번째 줄에는 $N$개의 집의 대문에 쓰여 있는 수 $A_i$가 공백을 사이에 두고 순서대로 주어진다. 세 번째 줄부터 $N+1$번째 줄까지는, 도로의 정보가 주어진다. $2+i$번째 줄에는 $i$번째 도로가 잇는 두 집의 번호 $a_i, b_i$에 대한 정보가 공백을 사이에 두고 주어진다. $N+2$번째 줄부터 $N+Q+1$번째 줄까지는 놀이에 대한 정보가 주어진다. $N+i+1$번째 줄에는 $i$번째 놀이를 시작할 집의 번호 $x_i$와, 끝낼 집의 번호 $y_i$가 공백을 사이에 두고 주어진다.

출력

첫 번째 줄부터 $Q$번째 줄에 걸쳐, $i$번째 줄에는 $i$번째 놀이의 결과를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

제한

$2\leq N \leq 1\,000$ $1\leq Q \leq 1\,000$ $1 \leq A_i \leq 1\,000\,000\,000$ ($1 \leq i \leq N$) $1 \leq a_i, b_i \leq N$ $1 \leq x_i, y_i \leq N$

예제

입력

3 2
10 9 1
1 2
2 3
1 3
3 1

출력

1091
1910

My Sol

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

def pathcheck(s, e):
    visit = [0]*(V+1)
    Q = deque()
    Q.append((s, [s]))

    while Q:
        u, path = Q.popleft()
        if u == e: return path
        if visit[u]: continue
        visit[u] = 1

        for v in G[u]:
            if visit[v]: continue
            Q.append((v, path+[v]))


V, Q = map(int, input().split())
doors = ['0'] + list(input().split())
G = [[] for _ in range(V+1)]
for _ in range(V-1):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)

for _ in range(Q):
    s, e = map(int, input().split())
    path = pathcheck(s, e)
    txt = ''
    for p in path:
        txt += doors[p]
        txt = str(int(txt) % 1000000007)
    print(txt)

BFS를 이용해 도착노드까지 가는 경로를 파악하고, 이 각각의 노드에 해당하는 수 문자열을 이어붙인 뒤, 숫자 변환하여 1000000007로 나눈 나머지를 txt로 재지정한다. 이를 path가 끝날 때까지 반복한다. 만약 매번 이 나누는 과정을 하지 않는다면 수가 너무 커져서 메모리 초과가 발생할 것이다.

매번 나누어 나머지를 구하는 것이 가능한 이유는 뒤에 오는 수 문자열이 123이라고 할 때 이전 txt의 값이 X보다 큰 (X+A)라고 해보자. 그렇다면 (X+A)123은 (X*123) + (A*123)이고, X를 X로 나누면 나머지는 0이므로 A*123이 되는 것이다. 다시 말하면 두 수의 문자열을 붙인 어떤 값 Y가 X보다 크다면, X를 나눈 나머지만 남겨도 되는 것이다.

결과

맞았습니다!!

모범답안

출처

import sys
from collections import deque

N, Q = map(int, input().split())
num = [""] + input().split()
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, next(sys.stdin).split())
    graph[a].append(b)
    graph[b].append(a)

mod = 1_000_000_007
for line in sys.stdin:
    x, y = map(int, line.split())
    v = [False] * (N + 1)
    v[x] = True
    queue = deque([(x, num[x])])

    while queue:
        c, n = queue.popleft()

        if c == y:
            print(int(n) % mod)
            break

        for adj in graph[c]:
            if not v[adj]:
                v[adj] = True
                queue.append((adj, n + num[adj]))

연산시간이 30%가량 되는 풀이를 발견해 풀이를 분석해보려 한다. 결정적으로 다른 부분은, 나는 경로를 매번 deque에 넣어주며 경로를 파악한 뒤, 하나하나 나머지를 구하며 수를 붙여주었는데, 이 분은 경로 대신 나머지를 자체를 구해서 붙여가며 deque에 넣어주었다는 것이다. 이 작은 한 가지가 연산 속도에 그렇게 큰 차이를 만드는 것이 놀라웠다.