백준1399 보물의 위치

문제

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

1399번: 보물의 위치

 

풀이

dig(x) 함수

x의 모든 자리수의 합은 x가 10이상일때 x보다 작을 수 밖에 없다.(예를들어 2자리수 10*x + y는 x + y 보다 크다.)

따라서 모든 x에 대해 dig(x)는 0~9로 수렴한다.

골드넘버는 0~9일 것이고 골드넘버*M은 M이 최대 1000일 것이므로 나오는 수들은 9000이하일 것이다.

따라서 unionfind를 이용해 0<=x<=9000에 대해 dig(x)가 최종적으로 몇이 나오는지를 다 저장해둔다.

 

골드넘버

골드넘버는 1부터 시작한다. 그다음 골드넘버도 M이 무엇이든지 1자릿수일것이다. 그 다음다음도 동일하다.

0~9의 골드넘버를 정점으로보고 모든 정점의 outdegree가 1인 간선이 10개인 유향그래프로 골드넘버의 변화를 모델링할 수 있다.(사실 0은 0아니면 dig(x)로 나오지 않으므로 무시해도 된다.)

모든 outdegree가 1인 그래프는 이 두 모양뿐이다.

모든 정점이 사이클을 이룬다.

일부 정점이 사이클을 이루고 나머지 정점은 사이클로 진입하는 방향이다.

0부터 9까지 반복하면서 한자릿수와 dig(한자릿수*M)을 이어주자.

 

진행방향

문제는 골드넘버들을 나누어도 방향이 4방향이므로 계산하기 힘들단 것이다.

방향은 y+ -> x+ -> y- -> x- 로 바뀐다. 작업을 4번시행할때 마다 원래 자기방향으로 다시 계산한다.

이 부분을 바꿔야한다.

 

0부터 9까지 반복하면서 한자릿수와 dig(한자릿수*M)을 이어주자.

 

특정 한자릿수에서 dig(한자릿수*M)을 4번시행했을때 결과와 이어주자.

그럼 특정 방향에서의 골드넘버 변화를 알 수 있다.

이는 희소배열로하든 하드코딩하는 편한대로 구현하면된다. 

이제 이 정보를 이용해 (각 방향의 시작 골드넘버)부터 시작해서 dfs를 돌린다.

만약 node1에서 node2를 방문하려할떄 node2가 방문처리된 정점이라면, node2~node1까지 사이클을 이루는 정점들이다. (시작)부터 node1전에 방문한 정점은 사이클을 이루지 않는다. (만약 node1 == (시작)이라면 전체사이클이다.)

각 방향의 시작골드넘버는 하드코딩하면알 수 있다. y+는 1이고 x+는 dig(1*M)이고 y-는 dig(dig(1*M))이고...

 

계산

이제 우린 사이클로 반복되는걸 찾았으므로 K<=10**9란 인풋을 처리할 수 있다.

1. 사이클로 진행하기 전까지 골드넘버들을 계산한다. 결과는 이 골드넘버들의 합이다.

2. 그러다 K가 작아서 만약 더 진행할 필요가 없다면 종료한다.

3. 이제 사이클이다. 사이클을 몇번 돌릴 수 있는지 본다. X번 돌릴 수 있다면 결과에 sum(cycle을 이루는 골드넘버의 합)*X을 더해준다.

4. 만약 남은 진행횟수가 있다면 사이클에서 더 진행해준다.

 

코드

import math
import sys
from collections import deque
from copy import deepcopy
from heapq import heappush, heappop
from itertools import combinations, permutations

input = sys.stdin.readline
# sys.setrecursionlimit()

# 수는 최대 9*M(9000)까지 나옴
# 루트가 1자리수인 트리로 수들을 다 치환 가능할 것이다. 따라서 dig(x)는 O(1)에 무슨 수인지 알 수 있다.
# y+ x+ y- x- 순으로 진행
# 규칙이 있을 것이니라..

# processing
parent = [i for i in range(9001)]


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


def union(x, y):
    x = find(x)
    y = find(y)
    if x > y:
        x, y = y, x
    parent[y] = x


def num2sum(n):
    s = str(n)
    r = 0
    for ss in s:
        r += int(ss)
    return r


for i in range(10, 9001):
    union(i, num2sum(i))
for i in range(9001):
    find(i)

for _ in range(int(input())):
    K, M = map(int, input().split())
    table = [[0] * 10 for _ in range(3)]
    for i in range(1, 10):
        table[0][i] = find(i * M)
    for i in range(1, 3):
        for j in range(1, 10):
            p = table[i - 1][j]
            table[i][j] = table[i - 1][p]
    start = [1, 0, 0, 0]  # y+ x+ y- x-
    for i in range(1, 4):
        start[i] = table[0][start[i - 1]]
    # 각자 데이터를 뽑아냄
    # 사이클까지 가는 경로, 사이클 따로
    before = [[] for _ in range(4)]
    cycle = [[] for _ in range(4)]
    for i in range(4):
        state = [-1] * 10
        stack = [start[i]]
        path = [start[i]]
        while stack:
            node = stack.pop()
            n = table[-1][node]
            if n in path:
                while path and path[-1] != n:
                    cycle[i].append(path.pop())
                cycle[i].append(path.pop())
            else:
                path.append(n)
                stack.append(n)
        while path:
            before[i].append(path.pop())
    for i in range(4):
        cycle[i].reverse()
        before[i].reverse()


    def get(k, i):
        # k번 움직였을때 총 얻는 gain
        # 각 방향마다 계산. k k-1 k-2 k-3을 넣으면 됨
        if k <= 0:
            return 0
        # case1: before로 다 해결되는 경우: 4*len(before[i])
        r = 0
        if 4 * len(before[i]) >= k:
            for j in range(len(before[i])):
                kk = j * 4 + 1
                if kk > k:
                    break
                r += before[i][j]
            return r
        # case2: 사이클 순환
        r += sum(before[i])
        k -= 4 * len(before[i])
        # 1 5 9 ... x <= k인 최대 x: 1 + 4*(t-1) = x <= k
        t = (k - 1) // 4 + 1
        # t = 사이클개수 * 사이클길이 + 나머지
        td = t // len(cycle[i])
        tm = t % len(cycle[i])
        r += sum(cycle[i]) * td
        for j in range(tm):
            r += cycle[i][j]
        return r


    print(get(K - 1, 1) - get(K - 3, 3), get(K, 0) - get(K - 2, 2))