Jin의 일상

programmers.co.kr/learn/courses/30/lessons/43165

문제 설명

1. 배열 변수인 numbers가 주어진다. ex) [1, 3, 4, 5, 2]

2. int형 변수인 target이 주어진다.

3. 각 numbers를 무작위로 더하거나 빼서 target 값과 같은 개수는?

문제 풀이

1. 모든 경우의 수를 찾아야 하므로 완전 탐색 문제 입니다.

2. 더하거나 뺐을 때 나오는 값을 재귀적으로 실행시킵니다.

3. 경우의 수가 만들어질 때 마다 target 값과 sum 값이 같은지 비교후 리턴 합니다.

  - 같다면, cnt를 1씩 올려줍니다.

4. cnt를 정답으로 제출합니다.

코드

def solution(numbers, target):
    def DFS(L, sum):
        nonlocal cnt
        if L == len(numbers):
            if sum == target:
                cnt += 1
            return
        else:
            plus = sum + numbers[L]
            DFS(L + 1, plus)
            minus = sum - numbers[L]
            DFS(L + 1, minus)
            
    cnt = 0
    DFS(0, 0) 
    return cnt

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=' ')