728x90
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)
'PS > Python' 카테고리의 다른 글
[BOJ_Python] 12907. 동물원 (0) | 2021.03.28 |
---|---|
[BOJ_Python] 12904. A와 B (0) | 2021.03.28 |
[BOJ_Python] 2583. 영역 구하기 (0) | 2021.03.22 |
[BOJ_Python] 10026. 적록색약 (0) | 2021.03.22 |
[BOJ_Python] 17298. 오큰수 (0) | 2021.03.11 |
최근댓글