11388. 최대공약수로 만들기

문제

설명

N의 수 A1,A2,...AN가 주어진다. 이 중 몇 개의 수를 없앨 때(하나도 없애지 않는 것은 가능하지만 모두 없애는 것은 안 된다.)

남은 수들의 최대공약수가 G가 되는 경우의 수를 구하는 프로그램을 작성하라.

만약 없앤 다음 수의 구성이 같아도, 인덱스가 다른 수를 없앴다면 서로 다른 경우로 본다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, G(1 ≤ N ≤ 500, 1 ≤ G ≤ 10^3)가 공백 하나로 구분되어 주어진다.

두 번째 줄에는 N개의 정수 A1,A2,...AN(1 ≤ Ai ≤ 10^3)이 공백 하나로 구분되어 주어진다.

출력

각 테스트 케이스마다 수들을 없애고 남들 수들의 최대공약수가 G가 되는 경우의 수를 출력한다.

이 수가 매우 커질 수 있으므로, 1,000,000,007(=109 + 7)로 나눈 나머지를 출력하도록 한다.

아이디어

처음에 일일이 세야하나 고민하다가, 다른 분의 답안을 보고 DP를 사용해서 쉽게 푸는 문제라는 것을 알게되었다.

일일이 세봤다가 실패.. 사실 특이케이스만 더 고려하면 풀수있을 것 같긴 한데 보통 그런 식으로 문제를 풀다보면

문제를 풀기위한 또다른 문제가 계속 생겨서 일찍이 포기..

아이디어는 이렇다.

임의의 N-1개의 수 A1, A2, ... A(N-1) 집합에서, 최대공약수가 G인 부분집합의 경우의 수가 dp[G]라고 할때,
새로운 수 AN이 참여했을 땐 dp 테이블이 어떻게 바뀔 것인가?

1부터 A의 최대값 1001 중 하나를 i라 할때, AN과 i의 최대 공약수가 x라 하자.

그렇다면 dp[i] (A(N-1)까지 집합에서의 최대공약수가 i인 부분집합의 경우의 수,)에 포함 된 모든 부분집합들은 An이 집합에 포함되면서 최대 공약수가 x인 부분집합으로 변한다.

예를 들어 부분 집합 [3,6,9]는 최대 공약수가 3인 집합(dp[3]의 한가지 경우)인데, 이 집합에 새로운 2나 1이 들어온다면
[3,6,9,2] 나 [3,6,9,1]은 최대 공약수가 1인 집합의 한가지 경우가 된다.

쉬운 예제로 dp를 하나하나 따라가보자

G = 1
A = [1,2,3]

1. 처음 A1, 1에 대해서는 자기 자신만 부분집합으로 셀 수 있으므로, dp[1] = 1
2. A2가 들어오면서 1과 2의 최대 공약수가 1이므로 dp[1] = 2가 된다. dp[2]도 자기자신이 가능하므로 dp[2] = 1
3. A3은 1과 최대공약수가 1이므로 dp[1] = dp[1]+dp[1] = 4가 된다.
   이후 2와도 최대공약수가 1이므로 dp[1] = dp[1]+dp[2] = 5가 되고 이후 dp[3] = 1

결국 dp는 [0,5,1,1]

이 방법은 처음의 G값과는 상관없이 주어진 A에서 모든 G에 대해서 쓸 수 있다.

A = [1,2,4] 라면

2번 A2까지는 같지만 A3에서 조금 다르다.
1과 4의 최대공약수가 1이므로 dp[1] = 4 이후 2와 4의 최대공약수가 2이므로 dp[2] = 2가 되고 이후 dp[4] = 1
dp[3]은 0인데, 위에 쓰여있는 방법대로만 하면 3과 4의 최대공약수가 1이라 dp[1]을 또 계산하게 되므로 dp[i]가 0보다 클때에만 연산을 진행한다.

이 경우 dp는 [0,4,2,0,1]

이런 방법으로 경우의 수를 쉽게 계산할 수 있다는 것을 배웠다.

구현

T = int(input())
i_list = []
const = 1000000007
for tc in range(T):
    i_list.append(list(map(int,input().split()))+list(map(int,input().split())))


def gdc(a,b):
    while b >= 1:
        a, b = b, a%b
    return a

for tc,I_list in enumerate(i_list):
    G = I_list[1]
    tmp = I_list[2:]
    anw = 0

    lendp = 1001
    dp = [0]*lendp
    for v in tmp:
    	# G만 볼 것이므로 v가 G로 나누어지지 않는 경우는 고려하지 않아도 된다.
        if not v%G:
        	# dp의 인덱스 idx에 대해
            for idx in range(lendp):
            	# 경우의 수가 1이라도 있는 경우에만 연산 진행
                if dp[idx] > 0:
                	# 새로 들어온 v와 idx의 최대공약수가 x이면
                    x = gdc(idx,v)
                    # dp[x]를 dp[idx]만큼 더해주자.
                    dp[x] = (dp[x]+dp[idx])%const
        # v 자체로도 1가지 경우는 만족하므로 +1
        dp[v] += 1
    print(f'#{tc+1} {dp[G]}')

실행

입력

4
3 2
2 2 2
3 1
2 2 2
9 1
1 2 3 4 5 6 7 8 9
5 3
6 2 9 15 99

출력

#1 7
#2 0
#3 488
#4 10

느낀 점

이런 문제는 직접 생각하기엔 어려우나 한번 감을 잡으면 이후엔 쉽게 써먹을 수 있을 것 같아서 포스팅하였습니다.
세상엔 나보다 똑똑하고 잘난 사람이 많으니 항상 겸손하게 배우는 자세를 유지해야겠다는 걸 또 한번 느낍니다..
정리하고 보니 확실히 이해가 잘 됩니다.

화이팅 ㅜㅜ