BAEKJOON : 10971, 13023, 14391, 9012

No. 10971

from itertools import permutations
import sys
import math

n = int(sys.stdin.readline())
city = []
res = []

for _ in range(n):
    city.append(list(map(int,sys.stdin.readline().rstrip().split())))

routes = [i+(i[0],) for i in list(permutations(range(n),n))]

for route in routes:
    sum = 0
    for i in range(n):
        if city[route[i]][route[i+1]] == 0:
            sum += math.inf
            break
        sum += city[route[i]][route[i+1]]
    res.append(sum)

print(min(res))

import sys
import math

def sum(route):
    global res
    temp = 0
    for i in range(n-1):
        temp += city[route[i]][route[i+1]]
    temp += city[route[-1]][route[0]]
    res = min(res, temp)

def permutation(level):
    if level >= n:
        if city[arr[-1]][arr[0]] != 0:
            sum(arr)
    else:
        for i in range(n):
            if visited[i] == True:
                continue
            elif level > 0 and city[arr[level-1]][i] == 0:  # out of index 방지를 위해 level > 0 을 and 연산자 왼쪽에 배치
                continue
            else:
                visited[i] = True
                arr[level] = i
                permutation(level+1)
                visited[i] = False

n = int(sys.stdin.readline())
city = []
res = math.inf
visited = [False] * n
arr = [0] * n

for _ in range(n):
    city.append(list(map(int,sys.stdin.readline().rstrip().split())))

permutation(0)
print(res)

from itertools import permutations
import sys
import math

def solution():
    n = int(sys.stdin.readline())
    city = []
    res = math.inf
    

    for _ in range(n):
        city.append(list(map(int,sys.stdin.readline().rstrip().split())))

    routes = list(permutations(range(n)))

    for route in routes:
        if city[route[-1]][route[0]] == 0:
            continue
        sum = 0
        flag = False
        for i in range(n-1):
            if city[route[i]][route[i+1]] == 0 or sum >= res:
                sum += math.inf
                flag = True
                break
            sum += city[route[i]][route[i+1]]

        if flag:
            continue

        sum += city[route[-1]][route[0]]
        res = min(res,sum)

    print(res)

solution() 

メモリの使用状況を確認するには、tracemallocモジュール(Pythonドキュメント)を使用します.
-関数で使用し、その役割ドメインを離れると、残りのメモリのみが消えます.

コードをコミットする前にタイムモジュールを使用して時間をチェックし、tracemallocモジュールを使用してメモリをチェックすることに慣れています.

No. 13023

1. Problem

2. My Solution

import sys
sys.setrecursionlimit(10**8)

def dfs(v,level, visited):
    visited[v] = True
    level += 1
    
    if level >= 5:
        print(1)
        exit()

    for u in range(n):
        if u in friendship[v] and visited[u] != True:
            dfs(u,level, visited)
    

n, link = map(int,sys.stdin.readline().rstrip().split())
friendship = [[] for _ in range(n)]
visited = [False] * n

for _ in range(link):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    friendship[a].append(b)
    friendship[b].append(a)

for i in range(n):
    visited_copy = visited.copy()
    dfs(i,0,visited_copy)

print(0)

上のコードを下から赤のパスに移動した場合、深さは5未満で、戻ってから青のパスに移動する必要がありますが、赤のパスの場合はTrueに設定しますので、青のパスでは実行できませんので、Falseに再初期化する必要があります

import sys

def dfs(v,level):
    visited[v] = True
    level += 1

    if level >= 5:
        print(1)
        sys.exit()

    for u in friendship[v]:
        if visited[u] == False:
            dfs(u,level)
            visited[u] = False
    
n, m = map(int,sys.stdin.readline().rstrip().split())
friendship = [[] for _ in range(n)]
visited = [False] * n

for _ in range(m):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    friendship[a].append(b)
    friendship[b].append(a)

for i in range(n):
    dfs(i,0)
    visited[i] = False

print(0)

BFSアルゴリズムは適用されません.Bから赤色経路はDFSを介して深さ5に到達できると仮定するが、BFSは深さ3に到達するしかない(

No. 14391

import sys

n, m = map(int,sys.stdin.readline().rstrip().split())
paper = []
res = 0

for _ in range(n):
    paper.append(list(map(int,list(sys.stdin.readline().rstrip()))))

for bit in range(1 << n*m):
    sum = 0

    # 가로 찾기
    for i in range(n):
        temp = 0
        for j in range(m):
            k = i * m + j
            if bit & (1 << k) == 0:                 # 가로라면
                temp = temp * 10 + paper[i][j]      # 숫자 뒤에 붙이기 위해 원래 존재하는 수에 *10 한뒤 덧셈
            else:                                   # 세로라면
                sum += temp
                temp = 0  
        sum += temp

    # 세로 찾기
    for j in range(m):
        temp = 0
        for i in range(n):
            k =  i * m + j
            if bit & (1 << k) != 0:                # == 1 하면 버그발생 
                temp = temp * 10 + paper[i][j]
            else:
                sum += temp
                temp = 0
        sum += temp
    
    res = max(res, sum)

print(res)                                   

No. 9012

import sys

def solution():
    test_n = int(sys.stdin.readline())

    for _ in range(test_n):

        stack = []
        flag = False

        for i in (list(sys.stdin.readline().rstrip())):
            if i == '(':
                stack.append(i)
            elif stack:
                stack.pop()
            else:               
                flag = True
                
        
        if stack or flag == True:   # ')' 먼저 나온경우 또는 스택에 '(' 가 남아있는 경우
            print("NO")
        else:
            print("YES")
                
solution()

import sys

def solution():
    
    stack = []

    for i in (list(sys.stdin.readline().rstrip())):
        if i == '(':
            stack.append(i)
        elif stack:
            stack.pop()
        else:               
            print("NO")
            return
            
    if stack:  
        print("NO")
    else:
        print("YES")

test_n = int(sys.stdin.readline())
for _ in range(test_n):
    solution()