Jin의 일상

www.acmicpc.net/problem/19942

풀이전략

이 문제는 두 가지 조건을 충족시켜야 하는 완전 탐색 문제입니다.

1. 최소 성분기준 충족 

2. 최소비용

완전 탐색에 사용된 조건은 다음과 같습니다.

1. 최소비용을 넘은 경우의 수에 대해서는 진행을 멈춥니다.

2. 탐색이 시작될 때 마다 최소 성분기준을 충족시키는지 확인합니다.

  - 최소 성분을 기준을 통과했다면 최소 비용과 사용된 인덱스 번호들을 갱신합니다.

3. 모든 경우의 수 탐색이 끝나면 종료됩니다.

아래 그림은  완전탐색에 사용한 노드 그래프입니다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def passOrNot(v, usedIdx):
    global mn
    for i in range(4):
        if req[i] > v[i]:
            return False
    mn = v[4]
    mnIdx.clear()
    mnIdx.extend(usedIdx)
    return


def DFS(L, v, usedIdx):
    global mn
    if v[4] >= mn:
        return
    if passOrNot(v, usedIdx):
        return
    if L == n:
        return
    else:
        usedIdx.append(L+1)
        for i in range(5):
            v[i] += data[L][i]
        DFS(L + 1, v, usedIdx)

        usedIdx.pop()
        for i in range(5):
            v[i] -= data[L][i]
        DFS(L + 1, v, usedIdx)

if __name__ =='__main__':
    n = int(input())
    req = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(n)]
    mn = 9999999
    mnIdx = []
    res = DFS(0, [0]*5, [])

    if mn == 9999999:
        print(-1)
    else:
        print(mn)
        for i in mnIdx:
            print(i, end=' ')