본문 바로가기
알고리즘 문제 풀이

[백준 19942] 2020 정올 1차 중등부 "다이어트"

by 다빈치코딩 2024. 3. 3.

목차

    반응형

    문제 출처 : https://www.acmicpc.net/problem/19942

     

    19942번: 다이어트

    식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각

    www.acmicpc.net

    이 문제는 2020년 정보올림피아드 1차 중등부 2번 문제 입니다.

    문제 이해하기

    단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 넘어서는 최소 가격을 찾으면 되는 문제 입니다.

    N의 크기가 15로 비교적 작기 때문에 브루트 포스나 백트래킹으로 쉽게 결과를 찾을 수 있습니다. 백트래킹을 통해 문제를 해결해 보겠습니다. 백트래킹에 대해 잘 모른다면 아래 링크를 통해 백트래킹 기법이 무엇인지 확인 바랍니다.

    https://wikidocs.net/206357

     

    07. 백 트래킹

    백트래킹(backtracking)은 모든 조합을 검색하여 원하는 결과를 얻는 알고리즘 입니다. 모든 경우의 수를 조사하고 조건에 맞지 않으면 이전 단계로 돌아가 다른 조합을 검색…

    wikidocs.net

    코드 작성하기

    직접 코드를 작성하면서 문제를 해결해 보겠습니다.

    입력 받기

    N = int(input())
    
    mp, mf, ms, mv = map(int, input().split())
    INF = 10e9
    mc = INF
    foods = [0]
    
    for i in range(N):
        tmp = tuple(map(int, input().split()))
        foods.append(tmp)
    

    식재료의 개수 N을 입력 받습니다. 다음으로 단백질, 지방, 탄수화물, 비타민의 최소 영양 성분 mp, mf, ms, mv를 입력 받았습니다. 최소 가격을 찾는 것이기 때문에 최소 가격 mc의 초기값은 가장 큰 값으로 하였습니다.

    그리고 N개의 줄에 단백질, 지방, 탄수화물, 비타민, 가격 5개의 값을 받아 foods라는 리스트에 넣었습니다. 이 때 foods에 0을 처음에 넣은 이유는 식재료의 번호는 1부터 시작하기 때문에 0을 넣어 입력값의 인덱스를 1번으로 하기 위해서 입니다.

    결과 출력

    ans = []
    visited = []
    
    f = [0, 0, 0, 0, 0]
    solve(0, f)
    
    if mc == INF:
        print(-1)
    else:
        print(mc)
        print(*ans)
    

    solve 라는 함수를 사용하여 결과를 출력해 줍니다. visited는 방문한 식재료를 확인하기 위한 리스트 입니다. ans는 최소 비용을 가지는 식재료 번호를 넣어두기 위해 만들었습니다. 최종적으로 가격인 mc가 INF라면 -1을 출력하고, 아니면 가격과 식재료 변호를 출력하도록 하였습니다.

    solve 함수에 들어가는 인자는 크게 두 가지 입니다. 첫 번째는 현재 식재료를 어디까지 탐색했는지 나타내기 위한 것입니다. 두 번째 들어가는 인자는 총 5개의 값으로 이루어진 리스트로 현재까지 더해진 영양 성분 4가지와 가격 입니다.

    solve 함수

    def solve(num, food):
        global mc, ans
    
        if mp <= food[0] and mf <= food[1] and ms <= food[2] and mv <= food[3] and food[4] < mc:
            mc = food[4]
            ans = visited.copy()
        
        for idx in range(num + 1, N + 1):
            fd = foods[idx]
            for i in range(5):
                food[i] += fd[i]
            
            visited.append(idx)
            solve(food, idx)
    
            for i in range(5):
                food[i] -= fd[i]
            
            visited.pop()
    

    핵심 함수인 solve 함수를 확인해 보겠습니다. 최소 가격 mc와 그 결과 리스트인 ans는 글로벌 변수로 두어 함수 안에서도 수정 가능하도록 하였습니다.

    식재료의 4가지 성분이 기준치 보다 위에 있고 가격이 싸다면 mc와 ans에 저장되도록 하였습니다. visited.copy() 함수를 사용하여 저장한 이유는 이렇게 하지 않으면 visited와 연동되어 값이 계속 바뀌기 때문 입니다. 얕은 복사에 관한 내용으로 얕은 복사에 대해 잘 모른다면 아래 링크를 통해 얕은 복사가 무엇인지 확인 바랍니다. 이어 깊은 복사까지 공부하는 것이 좋습니다.

    https://wikidocs.net/192439

     

    02. 얕은 복사(Shallow copy)

    [TOC] # 얕은 복사(shallow copy) 앞서 우리는 리스트를 대입 연산자( = ) 를 사용해서 복사해도 가변 객체라 제대로된 복사가 이루어지지 않는 다는 것을 알게…

    wikidocs.net

    이제 반복문을 통해 성분들을 계속 더해줍니다. 백 트래킹이기 때문에 방문이 끝나면 food의 성분에서 제외하고 방문 결과도 초기화 하면 됩니다.

    전체 코드

    N = int(input())
    
    mp, mf, ms, mv = map(int, input().split())
    INF = 10e9
    mc = INF
    ans = []
    visited = []
    
    foods = [0]
    for _ in range(N):
        foods.append(tuple(map(int, input().split())))
    
    def solve(num, food):
        global mc, ans
    
        if mp <= food[0] and mf <= food[1] and ms <= food[2] and mv <= food[3] and food[4] < mc:
            mc = food[4]
            ans = visited.copy()
        
        for idx in range(num + 1, N + 1):
            fd = foods[idx]
            for i in range(5):
                food[i] += fd[i]
            
            visited.append(idx)
            solve(food, idx)
    
            for i in range(5):
                food[i] -= fd[i]
            
            visited.pop()
    
    f = [0, 0, 0, 0, 0]
    solve(0, f)
    
    if mc == INF:
        print(-1)
    else:
        print(mc)
        print(*ans)
    
    반응형