[BOJ_Python] 12967. pqr (미해결)

SWEA의 문제 중 '러시아 국기 같은 깃발'과 유사하다고 생각한 문제다.

조합을 구해야겠다고 생각하고 풀었고 itertools를 사용한 방법, dfs를 사용한 방법으로 시도해 보았다.

 

그런데 메모리 초과 에러에 막혔다. ㅠㅠ
나중에 dp로 한번 해봐야겠다.

# Memory Exceed
# from sys import stdin
# from itertools import combinations
# N, K = map(int, stdin.readline().split())
# arr = list(map(int, stdin.readline().split()))
#
# perm = list(combinations(range(N), 3))
# result = 0
# for p, q, r in perm:
#     if not (arr[p] * arr[q] * arr[r])%K:
#         result += 1
# print(result)

# dfs 조합으로 구해보기
from sys import stdin, setrecursionlimit
setrecursionlimit(10**8)
N, K = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))

selected = [0] * 3
result = 0

def pqr(idx, cnt, selected):
    global result

    if cnt == 3:
        tmp = 1
        for s_idx in selected:
            tmp *= arr[s_idx]
        if tmp%K == 0:
            result += 1
        return

    # idx가 index 끝까지 왔다면 break
    if idx == N:
        return

    selected[cnt] = idx
    pqr(idx+1, cnt+1, selected)
    pqr(idx+1, cnt, selected)

pqr(0, 0, selected)
print(result)