[Python]DFS를 이용한 부분집합 구현 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def recur(idx):
    check[idx] = 1
    tmp.append(n[idx])
    if len(tmp) == 3:
        a = sorted(tmp)
        if sum(a) not in result:
            result.append(sum(a))
    else:
        for i in range(7):
            if check[i] == 0:
                recur(i)
                tmp.pop()
                check[i] = 0

# def subset():
#     for i in range(1<<7):
#         tmp2 = 0
#         cnt = 0
#         for j in range(7):
#             if i & (1<<j):
#                 tmp2 += n[j]
#                 cnt += 1
#         if tmp2 not in result and cnt == 3:
#             result.append(tmp2)


for t in range(int(input())):
    n = list(map(int, input().split()))
    result = []
    for i in range(len(n)):
        tmp = []
        check = [0] * 7
        recur(i)
    # subset()
    result.sort()
    print("#{} {}".format(t+1, result[-5]))
참고문제:5948. 새샘이의 7-3-5 게임

댓글

댓글 쓰기

이 블로그의 인기 게시물

[Recursive][Python]토너먼트알고리즘

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 def check (a, b, card): if card[a] is card[b]: return a if card[a] is 1 : if card[b] is 2 : return b else : return a elif card[a] is 2 : if card[b] is 3 : return b else : return a else : if card[b] is 1 : return b else : return a def rec (st, ed, card): if st is ed: return st l = rec(st, (st + ed) // 2 , card) r = rec((st + ed) // 2 + 1 , ed, card) return check(l, r, card) def main (): T = int(input()) for tc in range( 1 , T + 1 ): N = int(input()) card = list(map(int, input() . split())) print ( "#{} {}" . format(tc, rec( 0 , N - 1 , card) + 1 )) main() 4880. [파이썬 S/W 문제해결 기본] 5일차 - 토너...
자세한 내용 보기

[python]섬의 둘레구하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 direction = (( - 1 , 0 ), ( 1 , 0 ), ( 0 , - 1 ), ( 0 , 1 )) def sol (st_y, st_x): global w, h cnt = 0 for d in direction: next_y = st_y + d[ 0 ] next_x = st_x + d[ 1 ] if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w or MAP[next_y][next_x] == 0 : cnt += 1 return cnt while True: w, h = map(int, input() . split()) if (w, h) == ( 0 , 0 ): break MAP = [list(map(int, input() . split())) for _ in range(h)] answer = 0 for i in range(h): for j in range(w): if MAP[i][j] == 0 : continue answer += sol(i,j) print (answer) 아이디어는 단순하다. 모든 좌표를 순회하면서 주변이 땅으로 연결되지 않을때 cnt를 하나씩 증가시킨다.
자세한 내용 보기

[Python][DFS]숨바꼭질

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 # def bfs(n, k): # global MAX_VAL # time = 0 # queue = deque() # queue.append((n,time)) # check[n] = True # while queue: # curr_p, curr_t = queue.popleft() # for d in [-1, +1, curr_p]: # next_p = curr_p + d # if not check[next_p] and 0<=next_p<=MAX_VAL: # if next_p == k: # print(curr_t+1) # return # queue.append((next_p, curr_t+1)) # check.append(next_p) from collections import deque MAX_VAL = 100000 check = [False] * (MAX_VAL + 1 ) dist = [ - 1 ] * (MAX_VAL + 1 ) n, k = map(int, input() . split()) check[n] = True dist[n] = 0 q = deque() q . append(n) while q: curr_p = q . popleft() for next_p in [curr_p - 1 , curr_p + 1 , 2 * curr_p]: if 0 <= n...
자세한 내용 보기