Posts

def fill_nemo(d=0):
    global cnt
    if N*M == d:
        cnt += 1
        return
    
    y = d // M + 1
    x = d  % M + 1

    # 사각형이 완성 안되는 경우(넴모를 놓을 수 있는 경우)
    if matrix[y-1][x] == 0 or matrix[y-1][x-1] == 0 or matrix[y][x-1] == 0:
        # 다음 위치에 네모 생성
        matrix[y][x] = 1
        fill_nemo(d+1)
        matrix[y][x] = 0

    # 다음 위치에 네모 생성 X
    fill_nemo(d+1)
    

N, M = map(int, input().split())

matrix = [[0]*(M+1) for _ in range(N+1)]

cnt = 0
fill_nemo()

print(cnt)

test_case = int(input())

def chk_test():
    chk_a_list = [0] * k
    chk_b_list = [1] * k

    for w_i in range(w):
        is_success = False

        for d_i in range(d - k + 1):
            cur_chk = [film[tmp_i][w_i] for tmp_i in range(d_i, d_i + k)]
            if cur_chk == chk_a_list or cur_chk == chk_b_list:
                is_success = True
                break
        if not is_success:
            return False
    return True


def test_film(film, depth=0, cnt_inject=0, chk_list=[]):
    global min_inject
    
    if cnt_inject >= min_inject:
        return

    if chk_test():
        min_inject = min(min_inject, cnt_inject)
        return

    if depth >= d:
        return
    
    origin_membrane = film[depth][:]

    # 현재 층을 그대로
    test_film(film, depth + 1, cnt_inject)

    # 현재 층을 a로
    film[depth] = inject_a
    test_film(film, depth + 1, cnt_inject + 1)
    film[depth] = origin_membrane

    # 현재 층을 b로
    film[depth] = inject_b
    test_film(film, depth + 1, cnt_inject + 1)
    film[depth] = origin_membrane

for t in range(test_case):
    d, w, k = map(int, input().split())

    film = [list(map(int, input().split())) for _ in range(d)]
    
    inject_a = [0] * w
    inject_b = [1] * w

    min_inject = float('inf')

    test_film(film)
    print(f"#{t + 1} {min_inject}")

def max_subset_sum(arr):
    dp = [[0, 0] for _ in range(c + 1)]

    for num in arr:
        for j in range(c, num - 1, -1):
            if dp[j - num][0] + num > c:
                continue
            next_sq_value = dp[j - num][1] + num ** 2
            if next_sq_value > dp[j][1]:
                dp[j][0] = dp[j - num][0] + num
                dp[j][1] = next_sq_value
    _, max_sum = max(dp, key=lambda x: x[1])
    return max_sum

test_case = int(input())

for t in range(test_case):
    n, m, c = map(int, input().split())
    honey_map = [list(map(int, input().split())) for _ in range(n)]
    total_max = 0

    for fst_i in range(n):
        for fst_j in range(n - m + 1):

            fst_max = max_subset_sum(honey_map[fst_i][fst_j:fst_j + m])

            for snd_i in range(n):
                start = 0
                if snd_i == fst_i:
                    start = fst_j + m
                for snd_j in range(start, n - m + 1):
                    snd_max = max_subset_sum(honey_map[snd_i][snd_j:snd_j + m])

                    total_max = max(total_max, fst_max + snd_max)

    print(f"#{t + 1} {total_max}")

# 계산

def calculate(num1, num2, operator):

    if operator == '+':
        num1 += num2
    elif operator == '-':
        num1 -= num2
    elif operator == '*':
        num1 *= num2
    elif operator == '/':
        num1 = int(num1 / num2)
    return num1

# 수식 완성
def search_expression(i, result):
    if i == n:
        global max_num, min_num
        max_num = max(max_num, result)
        min_num = min(min_num, result)
        return

    for operator in operators:
        if operator_dict[operator] > 0:
            operator_dict[operator] -= 1
            search_expression(i + 1, calculate(result, nums[i+1], operator))
            operator_dict[operator] += 1



test_case = int(input())

for t in range(test_case):
    n = int(input()) - 1
    operators = ['+', '-', '*', '/']
    operator_dict = {operator: cnt for operator, cnt in zip(operators, map(int, input().split()))}

    nums = list(map(int, input().split()))

    max_num = float('-inf')
    min_num = float('inf')
    result_dict = {}
    visited = []

    search_expression(0, nums[0])

    print(f"#{t + 1} {max_num - min_num}")

test_case = int(input())

def search_recipe(index_list, n):
    if n == 1 :
        return [[i] for i in index_list]
    result = []
    for i in range(len(index_list) - 1):
        for j in search_recipe(index_list[i+1:], n - 1):
            result.append([index_list[i]] + j)
    
    return result


for t in range(test_case):
    n = int(input())
    min_diff = float('inf')

    recipe = [list(map(int, input().split())) for _ in range(n)]
    
    index_set = set(range(n))

    comb_list = [[0] + c for c in search_recipe(list(range(1, n)), n // 2 - 1)]

    for comb in comb_list:
        comb2 = list(index_set - set(comb))
        food1, food2 = 0, 0

        for i_idx, (i1, i2) in enumerate(zip(comb, comb2)):
            for j1, j2 in zip(comb[i_idx + 1:], comb2[i_idx + 1:]):
                food1 += recipe[i1][j1] + recipe[j1][i1]
                food2 += recipe[i2][j2] + recipe[j2][i2]
        min_diff = min(min_diff, abs(food1 - food2))

    print(f"#{t + 1} {min_diff}")

test_case = int(input())


# 제한 칼로리 내에서 최대의 맛
def search_best(hamburgers, sum_cal=0, sum_score=0):
    global max_score
    max_score = max(max_score, sum_score)

    for i, (score, cal) in enumerate(hamburgers):
        if sum_cal + cal > l:
            continue
        search_best(hamburgers[i + 1:], sum_cal + cal, sum_score + score)


for t in range(test_case):
    n, l = map(int, input().split())

    hamburgers = [list(map(int, input().split())) for _ in range(n)]

    max_score = 0

    search_best(hamburgers)

    print(f"#{t + 1} {max_score}")

word = input().upper()

counter = defaultdict(int)

max_cnt = 0
max_alpha = ''
same_chk = False

for a in word:
    counter[a] += 1
    if counter[a] > max_cnt:
        max_cnt = counter[a]
        max_alpha = a
        same_chk = False
    elif counter[a] == max_cnt:
        same_chk = True

if same_chk:
    print('?')
else:
    print(max_alpha)

탐색 완료: 1, 2, 3

이렇게 목표 건물이 4번이 queue에 들어와 탐색을 마치면 4번 건물을 지었다는 것이므로 탐색을 멈추고 저장해두었던 시간을 출력하면 된다.

이 문제의 입력으로 주어지는 건물들로 만들어진 그래프는 항상 방향성을 가지며, 항상 모든 건물이 건축 가능하도록 주어진다고 했기 때문에 acyclic이다. 즉 이 문제의 그래프는 DAG(Directed Acyclic Graph)이다. DAG에서 어떤 노드로 들어오는 간선의 개수를 indegree라고 하는데 이 indegree의 개수에 따라 정렬하는 것을 위상 정렬(topologicla sort)이라고 한다.

따라서 우리가 위에서 필요 건물(indegree)에 따라 정렬하여 시간을 계산한 것은 위상 정렬을 이용한 알고리즘인 것이다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.