문제 링크: https://leetcode.com/problems/sum-of-distances-in-tree/

문제

문제를 요약하자면 tree가 주어질 때 모든 정점으로부터의 거리가 최소가 되는 정점에서의 모든 정점으로까지의 길이의 합을 출력하는 문제가 되겠습니다.

직관

tree기 때문에 Cycle이 없습니다. 따라서 한 edge를 제거했을 때,  그래프로 나눠집니다.

A와 B를 잇는 edge가 있다고 가정해봅시다. 그리고, A쪽 그래프에있는 모든 노드로부터 A까지의 거리를 알 수 있다고 가정해봅시다.

그럼 B쪽 노드의 관점에서 봤을 때는 우리는 모든 A쪽 그래프의 노드로부터 B까지의 거리의 총합을 다음 수식으로 구할 수 있습니다. 

$$TotalDist_{A side} + NodeCnt_{A side}$$

왜냐하면 A쪽 노드로부터 B쪽 노드로 오는 모든 길은 edge A->B를 지날 수 밖이 없기 때문이죠.

접근법

그러므로 우리는 DP를 계산할 수 있습니다. 

노드 N과 S가 있을 때, edge (N,S)에 의해서 N쪽 graph와 S쪽 graph 로 나뉘게됩니다.

그리고
$cnt[n][s] =$ $n$ 쪽 그래프에 있는 노드의 수
$dist[n][s] =$ N쪽 그래프에서 S로 가는 총 거리의 합

라고 정의할 때 우리는 이 두 배열을 다음과 같은 방식으로 업데이트할 수 있습니다.

$G[n]$ 을 노드 N과 이어진 모든 이웃 노드들을 포함하고 있을 때

$$dp[n][s] = sum_{i \in G[n], i \neq s}(dp[n][i] + cnt[n][i])$$
$$cnt[n][s] = sum_{i \in G[n], i \neq s}(cnt[n][i])$$

로 계산되게 됩니다. 

복잡도

이 풀이는 시간복잡도와 공간복잡도가 오직 edge의 개수의 영향받으며, edge는 총 N-1개 존재합니다.

시간 복잡도: $O(N)$

공간 복잡도:  $O(N)$

코드

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        self.G = [[] for i in range(n)]
        
        for e in edges:
            self.G[e[0]].append(e[1])
            self.G[e[1]].append(e[0])
        
        ans = []
        for i in range(n):
            ans.append(self.dp(i, -1)[0])
        return ans
    
    @cache
    def dp(self, pnode, source):
        dist = 0
        cnt = 0
        for n in self.G[pnode]:
            if n == source:
                continue
            n_dist, n_cnt = self.dp(n, pnode)
            dist += n_dist + n_cnt
            cnt += n_cnt
        cnt += 1
        return dist, cnt

영문 솔루션

https://leetcode.com/problems/sum-of-distances-in-tree/discuss/2939374/Python-Super-Simple-O(N)-DP-Solution 

Codejam 문제 풀이

sub Title: (1) Round1

구글 code jam은 일반적으로 난이도 순으로 나오기때문에 순서대로 풀면된다.

순위

2000등 밖으로 밀려나서, 1A 라운드 통과는 못했다.

거의 4년만에 제대로된 대회에 참가하는것 같은데 그래서 그런지 정말 머리가 안돌아간다.

1B는 통과할만한 것같은데, 간만에 문제를 풀어서 그런가 문제 푸는속도도 코드도 영 맘에들지 않는다.

무엇보다 아이디어 떠오르는 속도가 정말 너무 많은 trial-and-error을 필요로한다.

Append Sort

문제는 아래에서 자세히 읽을 수 있다.

문제 설명

정수가 N개가 주어진다.

정수 N개를 정렬하고 싶은데, 정수끼리의 순서를 바꿀수 없다.

우리가수행할 수 있는 연산은 각 정수에다가 숫자들을 더하는 건데 예를 들면 123이 있다면 여기다가 4를 더해서 1234로만드는 이런연산이가능하다.

123 → 1234

이런 연산을 최소한으로 수행해서 strictly increasing order로 만들어라.

sample Input

Sample Output

설명:

첫번째는 아래처럼 추가하면 100, 700, 1000 으로 오름차순으로 만들수 있다.

100

7 → 700

10 → 1000

총 0을 4번 추가했고, 이거보다 적게 추가해서 오름차순으로 만들 수 없기 때문에 답은 4다 

솔루션 코드

for tc in range(int(input())):
    N = int(input())
    X = list(map(int, input().split(" ")))
 
    ans = 0
    for i in range(1, N):
        if X[i] > X[i-1]:
            continue
        s_b = list(str(X[i-1]))
        s_p_max = list(str(X[i]))
        s_p_min = list(str(X[i]))
        count = 0
        ori_len = len(s_p_max)
        while int("".join(s_b)) >= int("".join(s_p_max)):
            s_p_max += "9"
            s_p_min += "0"
            count += 1
        ans += count
        if int("".join(s_b)) < int("".join(s_p_min)):
            X[i] = int("".join(s_p_min))
        else:
            # same
            X[i] = X[i-1]+1
 
    print(f"Case #{tc+1}: {ans}")

그지처럼 풀었다.

첫번째 원소는 건드리지 않아도 되니까 range(1, N) 으로 시작한다. 시작부터 크다면 신경쓸필요없으니까 그리고 뒤를 9로 일단 채워나가면서(그 자리수에서 체울 수 있는 가장 큰 수) 될때까지 자리수를 늘려나간다.

그리고 늘려나간 최종 값중에서 가장 작은 값 (예를들자면, 10에서 2개의 digit을 추가했다면, 1099이 최대값, 1000이 최솟값이 된다.)이 배열의 이전 값 (s_b, X[i-1]) 보다 크다면 그게 답이 되기 때문에 X[i]에 그 값 자체를 넣어준다. int("".join(s_p_min))

만약 최솟값이 같다면, X[i-1]의 값에 +1해주면 된다. 이부분은 +1해줌으로서 다른자리까지 전부 변화시켜주려면 9여야하는데, 모두 9로 되어있는 경우는 14번 째 줄의

while int("".join(s_b)) >= int("".join(s_p_max))

에서 컷팅당한다. 즉 +1만해줘도된다. 

이해가 안가시면 질문주세요. 대충 설명드립니다.

Prime Time

문제는 아래에서 자세히 읽을 수 있다.

소수가 주어진다. (중복된 소수들도 주어진다.)

소수를 두 그룹으로 만들 것인데, 한 그룹은 덧셈으로, 한 그룹은 곱셈으로 모든 연산을 수행할것이다. 이 때 합을 한 그룹과 곱을 한 그룹의 계산 값이 같아야 한다.

예를 들자면

2 - 2개

3 - 1개

5 - 2개

7 - 1개

11 - 1개

가 주어졌을 때,

2+ 2 + 3 + 7 + 11 == 5 * 5

가 되고 두 그룹의 합은 25로 같다. 이렇게 만들 수 있는 가장 큰 값을 구하라.

중요한 인풋 설명

소수는 499 이하의 것들로만 주어진다.

소수는 서로다른 소수 95개 까지 주어질 수있으며, 각 소수는 여러개 존재할 수 있다.

Sample Input

Sample Output

설명:

첫번째 input은 2가 2개, 3이 1개, 5가 2개, 7이 1개 11이 1개다.

이 때, 더하기 그룹은 2, 2, 3, 7, 11을 선택하고, 나머지 곱하기 그룹은 5 5를 선택하면 최대값 25가 뽑인다. 그래서 답은 25

Test Set 1 솔루션 소스코드

$2≤N_1+N_2+⋯+N_M≤10$. (소수의 총 개수가 10개 이하)

from functools import reduce
for tc in range(int(input())):
    N = int(input())
    P = []
    for i in range(N):
        p_i, n_i = map(int, input().split())
        P += [p_i for j in range(n_i)]
    ans = 0
    for i in range(1 << len(P)):
        arr = list(enumerate([1 if i & (1 << j) else 0 for j in range(len(P))]))
        arr_mul = reduce(lambda x, y: x * y, [P[i] if v == 0 else 1 for i, v in arr])
        arr_sum = sum([P[i] if v == 1 else 0 for i, v in arr])
        if arr_mul == arr_sum:
            ans = max(ans, arr_mul)
    print(f"Case #{tc+1}: {ans}")

소수의 총 개수가 10개 이하다.

잘모를 땐 다해보자. 모든 소수를 분해한다. 0번그룹 1번그룹

그래서 두개의 곱과 합을 구한 후 두개가 같다면 ans로 출력한다.

Test Set 2 솔루션 소스코드

$2≤N_1+N_2+⋯+N_M≤100$. (소수의 총 개수가 100개 이하)

from functools import reduce
 
for tc in range(int(input())):
    N = int(input())
    P = []
    UP = {}
    for i in range(N):
        p_i, n_i = map(int, input().split())
        UP[p_i] = n_i
        P += [p_i for j in range(n_i)]
    all_sum = sum(P)
    ans = 0
    unique_p = UP.keys()
    for t in range(all_sum, 0, -1):
        is_fail = False
        may_ans = t
        tot = 0
        for p in unique_p:
            p_count = UP[p]
            while t % p == 0:
                t //= p
                p_count -= 1
                tot += p
                if p_count < 0:
                    is_fail = True
                if is_fail:
                    break
            if is_fail:
                break
        if t != 1:
            is_fail = True
        if not is_fail and all_sum - tot == may_ans:
            ans = may_ans
            break
    print(f"Case #{tc+1}: {ans}")

소스코드가 개판이다.

자 이제 어떻게 줄일 수 있을 지 생각해보자. 100개니까 모두를 해보는 건 불가능하다. ($2^{100}$ 은 안봐도 TLE)

합과 곱중 하나를 고정시켜야하는데, 생각해보면 모든 수의 합은 매우 작다. 그러니까 곱하는걸 선택할 때 많은 수를 곱할 수 없다.

100개를 다합쳐보면 최대 얼마가나올까?

$499 * 100 = 49900$ 밖에 안나온다.

그럼 모든 소수를 다더하고, 1씩 빼가면서 그 수를 만들 수 있는지 확인한다. 만약 만드는 것을 실패하면, 불가능하다는 것이고, 만드는 것을 성공하면 만드는데 든 소수의 합을 뺀 것이 지금의 수인지 체크하면 된다. 그 코드는 아래와 같다.

        if not is_fail and all_sum - tot == may_ans:
            ans = may_ans
            break

시간복잡도는 대충 49900 * len(unique_p) * log (49900) 정도 될껀데, 뒤에껀 대충 빼고, 계산해도 49,90,000 정도다. 매우적으니까 당연히 통과다. 문제는 테스트 셋 3인데...

Test Set 3 솔루션 소스코드

$2≤N_1+N_2+⋯+N_M≤10^{15}$. (소수의 총 개수가 $10^{15}$개 이하)

이거 보고 솔직히 아 당연히 수학문제겠지 하고 제꼈다. 구글 수학문제좋아하니까 그럴꺼라고 생각했다.

그런데 멍청했다.

from functools import reduce
for tc in range(int(input())):
    N = int(input())
    P = []
    UP = {}
    all_sum = 0
    for i in range(N):
        p_i, n_i = map(int, input().split())
        UP[p_i] = n_i
        all_sum += p_i * n_i
    ans = 0
    unique_p = UP.keys()
    for t in range(all_sum, max(0, all_sum-8982), -1):
        is_fail = False
        may_ans = t
        tot = 0
        for p in unique_p:
            p_count = UP[p]
            while t % p == 0:
                t //= p
                p_count -= 1
                tot += p
                if p_count < 0:
                    is_fail = True
                if is_fail:
                    break
            if is_fail:
                break
        if t != 1:
            is_fail = True
        if not is_fail and all_sum - tot == may_ans:
            ans = may_ans
            break
    print(f"Case #{tc+1}: {ans}")

거의 메인 로직은 똑같고 중요하게 추가된게 아래 이거 하나다.

for t in range(all_sum, max(0, all_sum-8982), -1):

생각해보면, 곱셈으로 아무리 빼고싶어도 소수를 빼는데 한계가 있다. 곱셈이 너무 커지니까. 그러니까 곱셈측에도 컷팅같은 느낌을 줄 수 있다.

잘 생각해보면 499를 $10^{15}$ 더해봤자 $499*10^{15}$ 이다. 아니 엄청 큰 숫자아니냐고? 곱셈의 세계에서는 매우 작은 숫자다.

그럼 소수 최대 몇개를 뺄 수 있을까. 를 계산해보면

$$\text{log}_2(499*10^{15})=17.xx$$

이긴한데, 사실 계산하기 귀찮으니까 아무리그래도 $499^{18}$ 보다는 작을거라고 생각할 수 있다. 그러니까 아무리 빼고싶어도 499를 18번보다 많이 뺄수없으며, 어떤 소수든 18개이상 빼면 전체합을 넘어가게된다.

즉 뺄수있는 것의 범위가 $499*18=8982$보다는 작게된다는 것이다.

그래서 정말 뺄수있는최소값을 range(all_sum-8982, all_sum) 로 잡으면 되는데, all_sum-8982 가 0보다 작을수있으니까 max를 씌워준것일 뿐이다.

이건 대회중에 떠올리지 못한 아이디어다. 답안지보고 아 수학아니었는데... 하고 너무 아쉬워서 딱 저 아이디어 추가하고 메모리문제좀개선해서 제출했떠니 바로 답이 뜨더라.

아쉽다아쉬워...

Hacked Exam

문제 해석을 잘못하고있다가 10분전에 해석을 완료했다;

테스트셋 1번은 그냥 긁을만했는데 긁었으면 비벼볼만했을텐데 아쉽다.

마무리

아쉽네. 다음번엔 더잘해야징. 1B에는 다음라운드갈수있지않을까.