해리의 데브로그

(SW 문제해결 응용 구현 - 백트래킹) SWEA 5209 - 최소 생산 비용

|

문제

  • SWEA 5209 - [파이썬 S/W 문제해결 구현 5일차] 백트래킹 - 최소 생산 비용
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

def DFS(y, sum):
    global result

    if y == N:
        if result > sum:
            result = sum
        return

    if result < sum:
        return

    for x in range(N):
        if not visited[x]:
            visited[x] = True
            DFS(y+1, sum + Data[y][x])
            visited[x] = False

TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Data = [list(map(int, input().split())) for _ in range(N)]
    visited = [0]*N
    result = 987654321

    DFS(0, 0)
    print('#%d %d'%(tc, result))

(SW 문제해결 응용 구현 - 백트래킹) SWEA 5208 - 전기 버스 2

|

문제

  • SWEA 5208 - [파이썬 S/W 문제해결 구현 5일차] 백트래킹 - 전기 버스 2
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

def DFS(num):
    global cnt, result

    if num >= N:
        if result > cnt:
            result = cnt
        return

    if result < cnt:
        return

    start = num
    life = Data[start]

    for i in range(start+life, start, -1):
        cnt += 1
        DFS(i)
        cnt -= 1


TC = int(input())
for tc in range(1,TC+1):
    Data = list(map(int, input().split()))
    N = Data[0]
    result = 987654321
    cnt = 0

    DFS(1)

    print('#%d %d'%(tc, result-1))

(SW 문제해결 응용 구현 - 분할 정복) SWEA 5207 - 이진 탐색

|

문제

  • SWEA 5207 - [파이썬 S/W 문제해결 구현 4일차] 분할 정복 - 이진 탐색
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

TC = int(input())
for tc in range(1, TC+1):
    N, M = map(int, input().split())
    N1 = sorted(list(map(int,input().split())))
    M1 = list(map(int, input().split()))

    cnt = 0
    for num in M1:
        start = 0
        end = N-1

        flag = 0
        while start <= end:
            mid = (start + end) // 2

            if num >= N1[mid]:
                if num == N1[mid]:
                    cnt += 1
                    break

                start = mid + 1
                if flag == 1: break
                flag = 1

            elif num < N1[mid]:
                end = mid - 1
                if flag == -1: break
                flag = -1

    print('#%d %d'%(tc, cnt))

(SW 문제해결 응용 구현 - 분할 정복) SWEA 5204 - 병합 정렬

|

문제

  • SWEA 5204 - [파이썬 S/W 문제해결 구현 4일차] 분할 정복 - 병합정렬
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

def merge_sort(Data):
    if len(Data) <= 1:
        return Data

    mid = len(Data) // 2
    left = merge_sort(Data[:mid])
    right = merge_sort(Data[mid:])
    return merge(left, right)

def merge(left, right):
    global cnt

    left_N, right_N = len(left), len(right)
    result = [0] * (left_N + right_N)
    left_i, right_i = 0, 0
    i = 0

    if left[-1] > right[-1]:
        cnt += 1

    while left_i != left_N and right_i != right_N:
        if left[left_i] <= right[right_i]:
            result[i] += left[left_i]
            i += 1
            left_i += 1
        else:
            result[i] += right[right_i]
            i += 1
            right_i += 1

    if left_i != left_N:
        while left_i != left_N:
            result[i] += left[left_i]
            i += 1
            left_i += 1

    if right_i != right_N:
        while right_i != right_N:
            result[i] += right[right_i]
            i += 1
            right_i += 1

    return result


TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Data = list(map(int, input().split()))
    cnt = 0
    Data = merge_sort(Data)

    print('#%d %d %d'%(tc, Data[N//2], cnt))

SWEA 1865 - 동철이의 일분배

|

문제

  • SWEA 1865 - 동철이의 일 분배
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

  • 백트레킹 문제. 프루닝 조건을 넣어주지 않으면 시간 초과가 발생한다.
def MyCalc(y):
    global sub_result, result

    if sub_result <= result:
        return

    if y == N:
        result = sub_result
        return

    for x in range(N):
        if not visited[x]:
            if Table[y][x] == 0:
                continue
            else:
                sub_result *= (Table[y][x]/100)
                visited[x] = True
                MyCalc(y+1)
                sub_result /= (Table[y][x]/100)
                visited[x] = False


TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Table = [list(map(int, input().split())) for _ in range(N)]
    visited = [0] * N
    sub_result, result = 1, 0
    MyCalc(0)
    print('#%d %0.6f'%(tc, round(result*100, 6)))