척척석사의 코딩기록

dp로 풀 수 있는 문제다.

솔직히 시간과 메모리만 충분하다면 itertools로 간단하게 계산할 수도 있지만, 더욱 편리함을 위해서 dp로 해결하고자 한다.

문제는 이하와 같다.

즉, 제한된 갯수의 a와 z가 있는 상황에서 K번째 문자열은 무엇인가? 라는 문제가 되겠다.

이 문제를 조금 꼬아서 낸다면 a와 z를 전부 사용하지 "않는" 경우에 대해서 생각해보는 것도 재밌을 것 같다.

일단 주어진 문제에 충실해지기로 한다면, 해답은 다음과 같다.

import math
N,M,K = map(int,input().split())

def f(k):
    # 문자열 개수 초과하는 경우
    t = math.factorial(N+M) // (math.factorial(N) * math.factorial(M))
    if t < k:
        return -1
    dp = [[1 for _ in range(0, M + 1)] for _ in range(0, N + 1)]
    dp[0][0] = 0

    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    answer = ""
    n, m = N, M
    while (n > 0 or m > 0):
        if (n == 0 or m == 0):
            answer += 'a' * n
            answer += 'z' * m
            break
        else:
            if k <= dp[n - 1][m]:
                answer += "a"
                n -= 1
            else:
                k -= dp[n - 1][m]
                answer += "z"
                m -= 1
    return answer

print(f(K))

첫번째 분기에서, 먼저 K가 만들 수 있는 index인지 판단하는 알고리즘을 넣어준다.

만들 수 있는 index라는 것을 알게 되었다면, dp를 만들어 준다.

dp를 만들어준 이후에는 이 문자열이 어디쯤에 위치해있는지 확인해볼 필요가 있다.

a로 시작하는 문자열은 "반드시" z로 시작하는 문자열보다 앞에 오기 때문에, 다음과 같은 방식으로 분기를 나눠주면 되겠다.

조금 더 풀어쓰면, dp[n][m] = dp[n-1][m] + dp[n][m-1]로 이루어지는데

dp[n-1][m]은 a를 n-1개, z를 m개 쓴 문자열이고 dp[n][m-1]은 a를 n개, z를 m-1개 쓴 문자열들의 갯수이다.

즉, dp[n][m]은 dp[n-1][m]에 포함된 문자열의 가장 앞에 "a"를 붙인 것이고 (이 다음에 !)

dp[n][m-1]에 포함된 문자열의 가장 앞에 "z"가 붙여진 것들로서 이루어진다고 볼 수 있겠다.

위에서 설명했듯이, dp[n][m]에 포함된 친구들을 생각해본다면

"a" + dp[n-1][m][0] , ...., "a" + dp[n-1][m][-1]     < a로 시작하는 애들 

"z" + dp[n][m-1][0] , ...., "z" + dp[n][m-1][-1]     < z로 시작하는 애들

이 순서대로 정렬되어있다는 것을 확인할 수 있겠다.

이러한 방식으로 점점 K가 어디에 존재하는지 확인하는 방식으로 진행하면 되겠다.

결국 이 문제에서 중요한것은, 칠판에 쓰인 숫자들의 "최소공배수"는 얼마인가? 라는 것으로 귀결된다.

여기서 중요한 것은,

1. 칠판에 쓰인 숫자들이 얼마정도 중복되어 있는가? 그렇다면 중복되어 있지 않은 숫자들은 무엇인가?

2. 최소공배수를 어떻게 구할 것인가? 

최소공배수에 대한 아이디어는 공약수의 차수를 비교하는 방식으로 하면 좋을 것 같다.

답안의 코드는 다음과 같다.

import sys
from collections import defaultdict
input = sys.stdin.readline
p = 1_000_000_007
number = [False for _ in range (0,1001)]
prime_number = []
for i in range (2, 1001):
    if number[i] == False:
        prime_number.append(i)
        for j in range (2*i, 1001, i):
            number[j] = True

T = int(input())
for _ in range (0,T):
    numbers = defaultdict(int)
    N = int(input())
    num = list(map(int,input().split()))
    answer = 1
    for x in num:
        numbers[x] = 1
    num_list = list(numbers.keys())
    #num_list가 갯수를 줄인것
    answer = defaultdict(int)
    for x in num_list:
        while x != 1:
            for y in prime_number:
                cnt = 0
                while x % y == 0:
                    x //= y
                    cnt += 1
                answer[y] = max(answer[y], cnt)
    ans = 1
    for x in answer:
        ans *= (x ** answer[x])
        ans %= p
    print(ans % p)

DP를 적극적으로 활용하면 좋은 문제가 되겠습니다.

정수들의 조건이 생각보다 널널하게 주어져있었던지라, 전부 곱해줘도 10 * 100 * 1000 = 10 ** 6입니다.

계산에 있어서는 크게 문제가 없을 것 같네요.

해답 코드는 다음과 같습니다.

N,M,K = map(int,input().split())
p = 10 ** 9 + 7
card = list(map(int,input().split()))
card.sort()
#K로 나눈 나머지의 갯수를 카운팅 하면 되겠다, 양의 정수이므로 0이 들어가 있는 경우는 카운팅하지 않는 것으로 한다
cnt = [0 for _ in range (0,K)] #이전 단계 저장하기 위함
for i in range (0,N):
    if card[i] != 0:
        cnt[card[i] % K] += 1
#위 작업으로 한자리수인것들을 생각해보면?

for _ in range (1, M):
    new_cnt = [0 for _ in range (0,K)]
    for i in range (0,K):
        for j in range (0,N):
            t = (10 * i + card[j]) % K
            #t는 K로 나눈 나머지를 indicate
            new_cnt[t] += cnt[i]
    cnt = new_cnt

print(cnt[0] % p)

첫번째 반복문을 통해서 1자리의 K의 배수를 저장해줍니다.

두번째 반복문에서는 2자리 이후의 K의 배수를 카운팅해주겠습니다.

new_cnt라는 리스트를 새롭게 설정해주면서 다음과 같이 진행하면 되겠습니다.

문제는 다음과 같습니다.

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

즉, 어떤 명령어마다 인덱스에 해당되는 수를 바꿔주면서 바뀐 수열이 등차수열인지, 등비수열인지 확인하는 프로그램을 짜는 것이 목표가 되겠습니다.

만약 어떠한 수열이

1. 등차수열 -> 공차가 전부 동일하다는 것

2. 등비수열 -> 공비가 전부 동일하다는 것

이 부분에 포커싱을 하게 된다면 해당하는 수열이 어떠한 수열인지 확인하기 굉장히 간편해지겠습니다.

import math
import sys
from collections import defaultdict
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
difference = defaultdict(int)
divide = defaultdict(int)

for i in range(0, len(A) - 1):
    t = A[i + 1] - A[i]
    difference[t] += 1
    s = math.gcd(A[i + 1], A[i])
    s1, s2 = A[i + 1] // s, A[i] // s
    divide[(s1, s2)] += 1

for i in range(0, M):
    idx, x = map(int, input().split())
    idx -= 1
    if idx == 0:
        difference[A[1] - A[0]] -= 1
        s = math.gcd(A[1], A[0])
        s1, s2 = A[1] // s, A[0] // s
        divide[(s1, s2)] -= 1

        A[0] = x
        difference[A[1] - A[0]] += 1
        s = math.gcd(A[1], A[0])
        s1, s2 = A[1] // s, A[0] // s
        divide[(s1, s2)] += 1

    elif idx == N - 1:
        difference[A[-1] - A[-2]] -= 1
        s = math.gcd(A[-1], A[-2])
        s1, s2 = A[-1] // s, A[-2] // s
        divide[(s1, s2)] -= 1

        A[-1] = x
        difference[A[-1] - A[-2]] += 1
        s = math.gcd(A[-1], A[-2])
        s1, s2 = A[-1] // s, A[-2] // s
        divide[(s1, s2)] += 1
    else:
        difference[A[idx] - A[idx - 1]] -= 1
        difference[A[idx + 1] - A[idx]] -= 1
        s = math.gcd(A[idx], A[idx - 1])
        s1, s2 = A[idx] // s, A[idx - 1] // s
        divide[(s1, s2)] -= 1
        s = math.gcd(A[idx + 1], A[idx])
        s1, s2 = A[idx + 1] // s, A[idx] // s
        divide[(s1, s2)] -= 1

        #이전값을 바탕으로 만들어진 것들 삭제 후 업데이트
        A[idx] = x
        difference[A[idx] - A[idx - 1]] += 1
        difference[A[idx + 1] - A[idx]] += 1
        s = math.gcd(A[idx], A[idx - 1])
        s1, s2 = A[idx] // s, A[idx - 1] // s
        divide[(s1, s2)] += 1
        s = math.gcd(A[idx + 1], A[idx])
        s1, s2 = A[idx + 1] // s, A[idx] // s
        divide[(s1, s2)] += 1

    #아마 이 과정에서 시간 초과가 나오는 상황

    xx = A[1] - A[0]
    ss = math.gcd(A[1], A[0])
    yy = (A[1] // ss, A[0] // ss)
    t = A[1] / A[0]
    if difference[xx] == N - 1 and xx > 0 and int(xx) == xx:
        print("+")
    elif divide[yy] == N - 1 and yy[0] > 0 and yy[1] > 0 and t == int(t):
        print("*")
    else:
        print("?")

첫번째 반복문에서 기존 주어진 수열에서 인접항간의 차와 공비를 나타낼 수 있는 tuple을 저장해주고

다음 반복문에서는 주어진 idx에 해당하는 작업을 수행해줍니다.

(이때 주어지는 idx가 가장 처음인지, 마지막인지, 그렇지 아닌지 케이스를 나눠줘야합니다. 바꿔줘야하는 갯수가 다르기 때문입니다.)

마지막 #이후에서는 제가 이전에 실패했던 부분인데 다음과 같은 방식으로 체크를 했더니 문제가 풀리게 되었습니다.

문제는 다음과 같습니다.

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

Typical한 구현 문제였고, 케이스를 잘 나누어주면서 풀어주면 되겠습니다.

이러한 문제들의 경우, 몇가지 특이한 케이스가 어디로 이동하게 되는지 체크하면, 규칙성이 눈에 보이기 쉬운 문제 같습니다.

해답 코드는 아래와 같습니다.

import sys
input = sys.stdin.readline

N, M, R = map(int,input().split())
mat = []
for _ in range (0,N):
    a = list(map(int,input().split()))
    mat.append(a)
def oper(k,mat):
    column = len(mat)
    row = len(mat[0])
    if k == 1: #상하반전
        new_mat = []
        for i in range (column-1,-1,-1):
            new_mat.append(mat[i])

    elif k == 2: #좌우반전
        new_mat = []
        for i in range (0,column):
            new_col = []
            for j in range (row-1,-1,-1):
                new_col.append(mat[i][j])
            new_mat.append(new_col)

    elif k == 3: #오른쪽으로 90도 회전
        new_mat = [[0 for _ in range (0,column)] for _ in range (0,row)]
        for i in range (0,column):
            for j in range (0,row):
                new_mat[j][column-1-i] = mat[i][j]

    elif k == 4: #왼쪽으로 90도 회전
        new_mat = [[0 for _ in range(0, column)] for _ in range(0, row)]
        for i in range (0,column):
            for j in range (0,row):
                new_mat[row-1-j][i] = mat[i][j]

    elif k == 5 or k == 6: #4개로 나눈 뒤에 시계방향 회전
        n = column // 2
        m = row // 2
        new_mat = [[0 for _ in range (0,row)] for _ in range (0,column)]
        block_1, block_2, block_3, block_4 = [],[],[],[]
        for i in range (0,n):
            t = []
            for j in range (0,m):
                t.append(mat[i][j])
            block_1.append(t)

        for i in range (0,n):
            t = []
            for j in range (m,row):
                t.append(mat[i][j])
            block_2.append(t)

        for i in range (n,column):
            t = []
            for j in range (0,m):
                t.append(mat[i][j])
            block_4.append(t)

        for i in range (n,column):
            t = []
            for j in range (m,row):
                t.append(mat[i][j])
            block_3.append(t)

        #분할
        if k == 5:
            for i in range (0,column):
                for j in range (0,row):
                    if 0 <= i < n and 0 <= j < m:
                        new_mat[i][j] = block_4[i][j]
                    elif 0 <= i < n and m <= j < row:
                        new_mat[i][j] = block_1[i][j-m]
                    elif n <= i < column and m <= j < row:
                        new_mat[i][j] = block_2[i-n][j-m]
                    elif n <= i < column and 0 <= j < m:
                        new_mat[i][j] = block_3[i-n][j]

        elif k == 6:
            for i in range (0,column):
                for j in range (0,row):
                    if 0 <= i < n and 0 <= j < m:
                        new_mat[i][j] = block_2[i][j]
                    elif 0 <= i < n and m <= j < row:
                        new_mat[i][j] = block_3[i][j-m]
                    elif n <= i < column and m <= j < row:
                        new_mat[i][j] = block_4[i-n][j-m]
                    elif n <= i < column and 0 <= j < m:
                        new_mat[i][j] = block_1[i-n][j]
    return new_mat

cmd = list(map(int,input().split()))
for i in range (0,R):
    mat = oper(cmd[i],mat)

for i in range (0,len(mat)):
    print(*mat[i])

일본에 다녀오고, 여러가지 생각을 정리하면서 간만에 올리는 포스팅이 되겠습니다.

문제는 다음과 같습니다.

즉, 이전에 지나오지 않았던 발판으로 얼만큼 늘어날 수 있는가? 라는 문제가 되겠습니다.

백트래킹의 교과서 같은 문제 중 하나인 것 같습니다.

시간이 좀 여유로울 것 같아서 여러가지 오답 코드를 작성했습니다만 (이전에 방문했던 포인트들을 리스트로 만들어서 하나하나 체크한다던지)

결국 등장한 알파벳을 True로 세팅하고, 아닌 경우에는 False로 체크하는 방식으로 진행하는것이 제일 좋아보였습니다.

코드는 다음과 같이 나오겠습니다.

R,C = map(int,input().split())
mapp = []
for _ in range (0,R):
    a = input()
    mapp.append(a)

moving = [(0,1),(-1,0),(1,0),(0,-1)]
ans = 0
visited = [False for _ in range (0,26)]
visited[ord(mapp[0][0]) - 65] = True
cnt = 1
def bfs(n,m):
    global ans
    global visited
    global cnt
    ans = max(ans, cnt)
    for k in range (0,4):
        nn,mm = n + moving[k][0], m + moving[k][1]
        if 0 <= nn < R and 0 <= mm < C and visited[ord(mapp[nn][mm]) - 65] == False:
            visited[ord(mapp[nn][mm])-65] = True
            cnt += 1
            bfs(nn,mm)
            visited[ord(mapp[nn][mm])-65] = False
            cnt -= 1
bfs(0,0)
print(ans)

즉, 제한된 금액을 기반으로 최대의 숫자를 만들어내는 프로그램을 작성하는 것이 되겠다.

스펙은 다음과 같습니다.

파이썬에서는 그래도 나름 괜찮은 퍼포먼스였던 것 같다. 메모리를 더 줄일 수 있다면 좋을 것 같다.

그리고 작성한 프로그램은 다음과 같다.

N = int(input())
value = list(map(int,input().split()))
M = int(input())

dp = [-1 for _ in range (0, 51)]

for i in range (0,N):
    if M - value[i] >= 0:
        dp[M-value[i]] = max(dp[M-value[i]], i)

for i in range (50,-1,-1):
    if dp[i] != -1:
        main_number = str(dp[i])
        for j in range (0,N):
            if i - value[j] >= 0:
                new_number = main_number + str(j)
                dp[i - value[j]] = max(dp[i - value[j]], int(new_number))

ans = max(dp)
print(ans)

이 방법은 냅색 문제와 비슷한 느낌으로 풀었던 것 같다.

dp라는 array를 만들어 둔 뒤, 각각의 index가 "보유한 돈"을 나타낸다고 생각하자.

그리고 dp[index]는 보유한 돈을 바탕으로 가장 큰 수를 나타낸다고 하자.

첫번째 반복문에서 "한자릿수"의 카드들을 먼저 배치하는 상황이 되겠다.

두번째 반복문은, 50 -> 0 순으로 가지고 있는 돈이 적어지는 순으로 반복이 진행된다고 생각하면 좋을 것 같다.

무엇인가를 사는 이상 보유한 돈은 반드시 줄어들기 때문이다.  (마치 monotonically decreasing 같다)

main_number는 보유한 돈이 i일때 나타낼 수 있는 최대 숫자를 나타내고,

new_number는 이 최대 숫자 뒤에 어떤 숫자를 붙일 수 있을지 판단하면서 i - value[j]의 값과 대소를 비교하게 되겠다.

그리고 마지막으로 dp값에서 가장 큰 것을 찾아주면 되겠다.

원래 문제는 다음과 같습니다.

생각보다 순서대로 분기를 잘 나눠주면서 하면 될 것 같습니다.

from collections import defaultdict
import sys
import heapq
input = sys.stdin.readline

score_dae, score_gyu = 0,0
num_dae, num_gyu = defaultdict(int), defaultdict(int)
third_prime_dae, third_prime_gyu = [-1,-1,-1], [-1,-1,-1]


prime = defaultdict(int)
num = [False for _ in range (0,5000001)]
num[0], num[1] = True, True
for i in range (2,5000001):
    if num[i] == False:
        prime[i] = 1
        for j in range (2 * i, 5000001, i):
            num[j] = True
#prime에 소수 저장 완료

def check(n,i):
    global third_prime_gyu
    global third_prime_dae
    global score_gyu
    global score_dae
    if prime[n] == 0: #소수가 아닌 경우 페널티를 주는 방향으로
        if i == -1: #-1를 대웅이의 턴
            x = heapq.heappop(third_prime_gyu)
            if x == -1:
                score_gyu += 1000
                heapq.heappush(third_prime_gyu, -1)
            else:
                score_gyu += x
                heapq.heappush(third_prime_gyu, x)
        elif i == 1: #1을 규성이의 턴
            x = heapq.heappop(third_prime_dae)
            if x == -1:
                score_dae += 1000
                heapq.heappush(third_prime_dae, -1)
            else:
                score_dae += x
                heapq.heappush(third_prime_dae, x)
    else: #일단 소수를 말했는가?
        if num_dae[n] != 0 or num_gyu[n] != 0: #이전에 말해진 소수인 경우
            if i == -1:
                score_dae -= 1000
            elif i == 1:
                score_gyu -= 1000
        elif num_dae[n] == 0 and num_gyu[n] == 0: #이전에 나오지 않은 수
            if i == -1:
                num_dae[n] = 1
                heapq.heappush(third_prime_dae,n)
                heapq.heappop(third_prime_dae)
            elif i == 1:
                num_gyu[n] = 1
                heapq.heappush(third_prime_gyu, n)
                heapq.heappop(third_prime_gyu)
N = int(input())
for _ in range (0,N):
    a,b = map(int,input().split())
    check(a,-1)
    check(b,1)

if score_dae > score_gyu:
    print("소수의 신 갓대웅")
elif score_dae < score_gyu:
    print("소수 마스터 갓규성")
elif score_dae == score_gyu:
    print("우열을 가릴 수 없음")

1이상 백만 이하의 어떤 수가 주어졌을 때, 해당하는 수를 4개의 소수의 합으로 나타내는 문제가 되겠다.

여기서 한가지 알아두면 좋은 것이 골드바흐의 추측이다.

https://ko.wikipedia.org/wiki/%EA%B3%A8%ED%8A%B8%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%94%EC%B8%A1

여기에서 수치적인 분석에 의하면 10^18까지는 해당 추측이 성립한다고 한다 !

-> 백만정도는 이 수치 안에 포함되므로 어렵지 않다는 것을 알 수 있겠다.

즉, 케이스를 나눠본다면 다음과 같이 나눌 수 있겠다.

1. 주어진 수 N이 홀수 / 짝수 인가?

2-1. N이 홀수인 경우

짝수인 소수는 2 하나뿐이므로, 다음과 같이 케이스를 나눌 수 있겠다.

2-1-1. 4개의 숫자 중 2가 1개 존재하는 경우

그렇다면 N-2는 3이상의 세개의 소수의 합으로 나타내어지는가? 

계산의 편의를 위해, 이때는 세개 중 하나의 소수가 3이라고 해버리자.

그렇다면 N-5가 4이상인 짝수 일 때, 골드바흐의 추측을 인정한다면 나타낼 수 있다는 것이므로 소수의 집합을 반복문을 돌면서

N-5 = p1 + p2 (p1,p2는 소수)인지 확인해주면 되겠다.

2-1-2. 4개의 숫자 중 2가 3개 존재하는 경우

N-6이 소수인지 확인하면 되겠다.

2-2. 주어진 수가 짝수인 경우

마찬가지 짝수인 소수는 2만 존재하므로 다음과 같이 케이스를 나누자.

2-2-1. 4개의 숫자 중 2가 4개 존재하는 경우

이 경우에는 2,2,2,2로 나타내어진다는 것이므로, N이 8인지 체크

2-2-2. 4개의 숫자 중 2가 2개 존재하는 경우

2,2,p1,p2로 나타내어진다는 것이므로, N-4에 대해서 반복문을 순환해주면 되겠다. (2-1-1과 유사한 방법)

소스 코드는 다음과 같이 나온다.

import math
from collections import defaultdict
N = int(input())
def prime(n):

    num = [False for _ in range (0,n+1)]
    num[0] , num[1] = True, True
    m = int(math.sqrt(n) + 1)
    prime_number = []
    prime_num = defaultdict(int)
    for i in range (2, n+1):
        if num[i] == False and i != 2:
            prime_number.append(i)
            prime_num[i] += 1
            for j in range (i,n+1,i):
                num[j] = True
    #4이상의 짝수는 두 홀수인 소수의 합으로 나타낼 수 있다 -> Goldbach's conjecture

    #prime_number는 3이상의 소수들의 집합
    if n % 2 == 0:
        if n == 8:
            return [2,2,2,2]
        elif n - 4 >= 6: #3이상의 소수 2개의 합으로 이루어진 경우
            for x in prime_number:
                if prime_num[n-4-x] != 0:
                    return [2,2,x,n-4-x]

    elif n % 2 != 0:
        # 2가 3개 존재하고, 3이상의 소수가 1개 존재하는 경우
        if n - 6 in prime_number:
            return [2,2,2,n-6]
        else:
            #n-5를 2개의 소수의 합으로 나타내야하는 상황
            for x in prime_number:
                if prime_num[n-5-x] != 0:
                    return [2,3,x,n-5-x]
    return [-1]

print(*prime(N))

from collections import defaultdict
import math
N = int(input())
A = list(map(int,input().split()))
M = int(input())
B = list(map(int,input().split()))

div1, div2 = defaultdict(int), defaultdict(int)
#A를 위한것
def a(n):
    t = int(math.sqrt(n)) + 1
    for i in range (2,t):
        if n % i == 0:
            while n % i == 0:
                div1[i] += 1
                n //= i
    if n != 1:
        div1[n] += 1
    return

def b(n):
    t = int(math.sqrt(n)) + 1
    for i in range(2, t):
        if n % i == 0:
            while n % i == 0:
                div2[i] += 1
                n //= i
    if n != 1:
        div2[n] += 1
    return

for aa in A:
    a(aa)
for bb in B:
    b(bb)


num = list(div1.keys())
ans = 1

check = False
for x in num:
    if x in div2:
        ans *= (x ** min(div1[x], div2[x]))
        if ans >= 1_000_000_000:
            check = True
            ans %= 1_000_000_000
if check == True:
    y = len(str(ans))
    ans = "0" * (9-y) + str(ans)
    print(ans)
else:
    print(ans)

곱해져서 A와 B가 된다는 것은 본질적인 질문은 아니라고 생각되는 문제였다. 

(괜히 말이 더 어렵게 느껴지는 여지가 있을듯?)

A와 B라는 리스트가 주어져 있을 때, 각 요소들을 소인수분해 한 뒤에 최대공약수를 구하는 방침으로 구하면 되겠다.

결국 아이디어는 어렵지는 않은 문제인 것 같다.

A = x_1^{y_1} * x_2^{y_2} * ... * x_n^{y_n},  B = x_1^{z_1} * x_2^{z_2}* ... * x_n^{z_n}  (Each x_i is prime number)

이런 꼴로 주어져 있을때, A와 B의 최대공약수는

gcd(A,B) = x_1^{min(y_1, z_1)} * x_2^{min(y_2, z_2)} * ... * x_n^{min(y_n,z_n)} 이런 꼴로 나타내어진다는 것에 유의 !

사실, 공통인 소인수를 갖지 않는 경우에도 동일한 논리를 적용할 수 있다. ㅎㅎ.