Jinho Tech

그냥 백트래킹 형식으로 쉽게 풀었다. 

def dfs(depth):
    if depth == k:
        s.add(''.join(map(str, li)))
        return ;
    for i in range(n):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        check[i] = 0
        
n, k = int(input()), int(input())
nums = [int(input()) for _ in range(n)]
li, s = [], set()
check = [0]*n
dfs(0)
print(len(s))

기본적인 다이나믹 프로그래밍 & 재귀 문제이다.

dp = [[[0]*21 for a in range(21)] for b in range(21)]

def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    if dp[a][b][c]:
        return dp[a][b][c]
    if a < b < c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return dp[a][b][c]
    dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    return dp[a][b][c]

while 1:
    a, b, c = map(int, input().split())
    if a == b == c == -1:
        break
    print("w(%d, %d, %d) = %d"%(a, b, c, w(a, b, c)))

기본적인 트리 문제이다.

• 전위 순회한 결과 : (왼쪽 자식) -> (오른쪽 자식)
• 중위 순회한 결과 : (왼쪽 자식) -> (루트) -> (오른쪽 자식)
• 후위 순회한 결과 : (왼쪽 자식) -> (오른쪽 자식) -> (루트)

def preorder(node):
    print(node, end='')
    left, right = tree[node][0], tree[node][1]
    if left != '.':
        preorder(left)
    if right != '.':
        preorder(right)

def inorder(node):
    left, right = tree[node][0], tree[node][1]
    if left != '.':
        inorder(left)
    print(node, end='')
    if right != '.':
        inorder(right)
        
def postorder(node):
    left, right = tree[node][0], tree[node][1]
    if left != '.':
        postorder(left)
    if right != '.':
        postorder(right)
    print(node, end='')
                        
N = int(input())
tree = {}
for i in range(1, N+1):
    node, left, right = input().split()
    tree[node] = [left, right]
preorder('A'); print()
inorder('A'); print()
postorder('A'); print()