バックアップアルゴリズムの手順10(Brootfore)


  • 新規コンテンツ
  • いわゆるルーティング転送アルゴリズム


    これは,すべての場合に要求を満たす数のみを検索するアルゴリズムである.(簡単に言えば、すべてのエリアをブラウズします.)
    ソース:https://go-coding.tistory.com/67

    1)2798番ブラックジャック


    与えられたカードの中からランダムに3枚を選択し、Mに最も近い結果を出力する.
    N, M = map(int, input().split())
    Nums = list(map(int, input().split()))
    #결과물을 담을 리스트
    ans_list = []
    
    # 3중 반복을 통해 전체 탐색.
    for i in Nums:
        for j in Nums[Nums.index(i) + 1:]:
            for k in Nums[Nums.index(j) + 1:]:
                if i + j + k > M:
                    continue
                else:
                    ans_list.append(i + j + k)
    
    print(max(ans_list))

    2)2231号分解

    N = int(input())
    ans_list = []
    
    for i in range(N):
        num = i
        i_list = list(str(i))
        for j in i_list:
            num += int(j)
    
        if num == N:
            ans_list.append(i)
    
    if len(ans_list) != 0:
        print(min(ans_list))
    else:
        print(0)

    3)7568番ブロック

    N = int(input())
    student_list = []
    ans_list = []
    for i in range(N):
        student = list(map(int, input().split()))
        student_list.append(student)
    
    for j in student_list:
        rank = 1
        for k in student_list:
            if j[0] < k[0] and j[1] < k[1]:
                rank += 1
            else:
                continue
        ans_list.append(rank)
    
    answer = ''
    for rnk in ans_list:
        answer += str(rnk) + ' '
    print(answer[:-1])

    4)チェス盤1018を塗り直す

    N, M = map(int, input().split())
    # 입력한 행, 열 범위의 2차원 배열 생성
    all_list = [['B' for col in range(M)] for row in range(N)]
    
    for k in range(N):
        row = input()
        # 입력한 행 값을 위에서 만든 2차원 배열에 넣어줌
        for t in range(M):
            all_list[k][t] = [row[t]]
    
    # 각 경우 마다 바꿔야 되는 횟수를 저장하는 리스트
    cnt_list = []
    # 시작점의 좌표는 N,M에서 8을 빼고 1을 더해준 만큼의 범위로 설정된다.
    for x in range(N-7):
        for y in range(M-7):
            first = all_list[x][y]
            cnt = 0
            해당 시작점을 기점으로 첫번 째 [0][0] 칸의 색을 바탕으로 계산해주고, 이를 cnt_list에 담아준다.
            for i in range(8):
                for j in range(8):
                    if i % 2 == 0 and j % 2 == 0 and all_list[x + i][y + j] != first:
                        cnt += 1
                    elif i % 2 == 0 and j % 2 != 0 and all_list[x + i][y + j] == first:
                        cnt += 1
                    elif i % 2 != 0 and j % 2 == 0 and all_list[x + i][y + j] == first:
                        cnt += 1
                    elif i % 2 != 0 and j % 2 != 0 and all_list[x + i][y + j] != first:
                        cnt += 1
            cnt_list.append(cnt)
    		
            # 첫번 째 칸의 색을 바꿀 경우 또한 고려한다. (cnt는 1로 초기화한다. 이미 첫번 째 색을 바꿨기 때문.)
            cnt = 1
            if first == ['B']:
                all_list[x][y] = ['W']
            else:
                all_list[x][y] = ['B']
            first = all_list[x][y]
            for i in range(8):
                for j in range(8):
                    if i % 2 == 0 and j % 2 == 0 and all_list[x + i][y + j] != first:
                        cnt += 1
                    elif i % 2 == 0 and j % 2 != 0 and all_list[x + i][y + j] == first:
                        cnt += 1
                    elif i % 2 != 0 and j % 2 == 0 and all_list[x + i][y + j] == first:
                        cnt += 1
                    elif i % 2 != 0 and j % 2 != 0 and all_list[x + i][y + j] != first:
                        cnt += 1
            cnt_list.append(cnt)
    
    # 모든 경우의 수를 담아준 리스트에서 최솟값을 출력한다.
    print(min(cnt_list))

    5)1436号映画監督

    N = int(input())
    cnt = 0
    ans = 666
    
    # 입력한 N번 째 숫자를 얻을 때 까지 반복문을 돌려준다.
    # 단 1씩 더해가기 때문에 모든 경우의 수를 다 체크한다.
    while True:
        if '666' in str(ans):
            cnt += 1
        if cnt == N:
            print(ans)
            break
        ans += 1