[BOJ] 다이어트 - Compy's Blog

다이어트

TimeLimit	MemoryLimit	Condition	TAG
2s	512MB	(3 ≤ N ≤ 15 0 ≤ mp, mf, ms, mv ≤ 500 mp + mf + ms + mv > 0 0 ≤ p, f, s, v, c ≤ 500)	Backtracking

오늘은 조금 문제 푸는 과정을 보여드리고 싶어서 찍어봤습닏 ㅏ.. 평소에 골랜디 즐겨하는데요 그거 좀 보여드립니다.

풀이 영상

지금 영상을 보면 1분 정도쯤에 바로 브포의 가능성을 보고서 바로 작성하는 것을 볼 수 있습니다. 또 구조도 한 문제 해석 단계에서 대부분 끝내는 편이구요

어려운 문제의 경우 문제를 해석하고 풀이 과정을 머리로 그리는 시간이 오래걸립니다. 사실상 코드 작성 시간은 어떤 문제든 간에 1시간 이내로 끝내는 것이 대부분인데.. 짜잘한 문법 실수나 다른 +, - 이런거 실수하는 거 때문에 많이 시간을 먹을 때도 있습니다.

이번 문제는 약간 사전순 정렬을 뒤늦게 발견해서 백트래킹의 순서를 바꿔줬습니다. 또 price를 모르고 그냥 조건 되는대로 가다가 이상하다 싶어서 보니까 네.. 문제도 사실 잘못된 정보로 작성하다가 바꾸게 되었죠?

그래도 백트래킹이 가능하다는 것(최대 경우의 수가 많지 않음을 파악함.), 사전순 정렬(백트래킹 순서) 이거를 한번에 파악했다는 것부터 좋은 접근이었다고 생각합니다.

정답 코드

#include <iostream>
#include <queue>
using namespace std;


struct food{
    int p, f, s, v, price;
    bool visited;
    
    int sum(){
        return p+f+s+v;
    }
};



int n;
food foods[16];
food current, target;
food result;

vector<int> result_members;

bool complete(){
    return current.f >= target.f && current.p >= target.p && current.s >= target.s && current.v >= target.v;
}

void getResult(){
    if(current.price < result.price) {
        result.p = current.p;
        result.v = current.v;
        result.f = current.f;
        result.s = current.s;
        result.price = current.price;
        result_members.clear();
        for(int i = 0; i < n; i++) {
            if(foods[i].visited) result_members.push_back(i+1);
        }
    }
}


void solution(int current_idx){
    if(complete()) {
        getResult();
        return;
    }
    if(current_idx >= n) return;
    
    current.p += foods[current_idx].p;
    current.v += foods[current_idx].v;
    current.f += foods[current_idx].f;
    current.s += foods[current_idx].s;
    foods[current_idx].visited = true;
    current.price += foods[current_idx].price;
    solution(current_idx+1);
    
    current.p -= foods[current_idx].p;
    current.v -= foods[current_idx].v;
    current.f -= foods[current_idx].f;
    current.s -= foods[current_idx].s;
    foods[current_idx].visited = false;
    current.price -= foods[current_idx].price;
    solution(current_idx+1);
    
    
    
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    current = {0, 0, 0, 0, 0};
    cin >> n;
    cin >> target.p >> target.f >> target.s >> target.v;
    
    result = {1000000000, 1000000000,1000000000,1000000000,1000000000, 0};
    
    for(int i = 0; i < n; i++) {
        cin >> foods[i].p >> foods[i].f >> foods[i].s >> foods[i].v >> foods[i].price;
        foods[i].visited = false;
    }
    
    solution(0);
    
    if(result_members.empty()) cout << -1;
    else{
        cout << result.price << "\n";
        for(int i : result_members) cout << i << " ";
    }
    
    
    
    return 0;
}