백준 19942번 다이어트 (C++)

문제 링크 : https://www.acmicpc.net/problem/19942

19942번: 다이어트

 

이 문제의 로직은 크게 다음과 같다.

(1) 오름차순으로 방문 순서를 저장한다. 

이때 유의해야할점이, n=3의 경우 {1},{1,2},{1,2,3}까지 방문하고 다시 {1,2}로 돌아가지 않도록 주의해야한다. 이럴 경우 아무리 배열의 최대 범위가 15까지라고 하더라고 시간초과가 날 수 밖에 없다. 

(2) 순서를 저장함과 동시에 여탯껏 저장한 순서들의 칼로리 + 돈을 계산한다.

(2)-(2) 계산한 값이 목표 칼로리 이상하고 돈이 더 적게드는 경우라면 해당 값들을 정답으로 갱신해준다.

 

오름차순으로 정렬하는 로직의 경우, 백준 15654번 N과 M(5)를 풀어본 적이 있으면 쉽게 이해할 수 있다.

#15654번 N과 M(5) (C++)

 

문제 풀이는 다음과 같다.

1. 필요한 변수들을 선언하고 값을 입력한다.

struct food{
    int a,b,c,d,e;
};

int n,c1,c2,c3,c4,money=MAX,temp[16],ans_len=0,ans[16];
bool ch[16];
vector<food> v(16);

void input(){
    cin >> n;
    cin >> c1 >> c2 >> c3 >> c4;
    for(int i=1; i<=n; i++){
        cin >> v[i].a;
        cin >> v[i].b;
        cin >> v[i].c;
        cin >> v[i].d;
        cin >> v[i].e;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    bt(1,1);
    ...
}

 

2. 입력을 마쳤으면 Back Tracking을 진행한다. Back Tracking의 코드는 다음과 같다.

void bt(int cnt, int order){
    for(int i=cnt; i<=n; i++){ // 1
        if(!ch[i]){ // 2
            ch[i] = true; // 3
            temp[order] = i; // 4
            calculate(order); // 5
            bt(temp[order],order+1); // 6
            ch[i] = false; // 7
        }
    }
    return;
}

(1) 마지막으로 방문한 위치를 기준으로 for문을 진행한다. 이는 오름차순으로 값을 출력함과 동시에, 방문했던 루트는 재방문을 하지 않기 위함이다. 

(2) 방문한 적이 없는 경우에 조건문으로 들어간다. 이는 방문했던 루트는 재방문하지 않기 위함이다.

(3) 방문 표시를 해준다.

(4) 정답을 저장할 배열의 '현재 순서'에 현재 방문 위치를 저장한다.

(5) 정답이 저장된 배열의 현재 순서 (= 현재까지 정답값 최대 범위)에 기준을 두어 칼로리를 계산한다 (아래 3번 해설 참고) 

(6) 칼로리 계산을 종료하고 다음 순번으로 이동한다. 이때 for문이 새로 진행되야 하는 범위는 현재 저장한 값의 뒤에 있는 숫자들만 해당되므로 (=갔던 곳의 재방문을 피하기 위해서), cnt는 temp[order]로 갱신해준다.

(7) 방문 표시를 해제해준다.

 

3. 아래는 칼로리를 계산하는 calculate함수이다.

void calculate(int len){
    int t1=0,t2=0,t3=0,t4=0,t5=0;
    for(int i=1; i<=len; i++){ // 1
        t1 += v[temp[i]].a;
        t2 += v[temp[i]].b;
        t3 += v[temp[i]].c;
        t4 += v[temp[i]].d;
        t5 += v[temp[i]].e;
    }
    if(t1>=c1&&t2>=c2&&t3>=c3&&t4>=c4&&money>t5){ // 2
        money = t5;
        for(int i=1; i<=len; i++){
            ans[i] = temp[i];
        }
        ans_len = len; // 3
    }
    return;
}

(1) 현재까지 저장된 정답 배열의 길이를 기준으로 칼로리를 계산한다.

(2) 칼로리와 돈이 정답 기준을 만족시키면 식재료 순서와 돈을 새로 갱신해준다.

(3) 이때 최종적으로 출력해야하는 정답 배열의 범위를 파악하기 위해, 현재 저장된 정답배열의 길이를 별도로 저장해준다.

 

4. 모든 연산이 끝나고 다시 main함수로 복귀했을 때 ans_len의 길이가 0보다 클 경우, 정답이 존재한다는 뜻이므로 정답을 출력한다.

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    bt(1,1);
    if(ans_len>0){
        cout << money << "\n";
        for(int i=1; i<=ans_len; i++) cout << ans[i] << " ";
        cout << "\n";
    }
    else cout << -1 << "\n";
    return 0;
}

 

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 1e9
using namespace std;

struct food{
    int a,b,c,d,e;
};

int n,c1,c2,c3,c4,money=MAX,temp[16],ans_len=0,ans[16];
bool ch[16];
vector<food> v(16);

void calculate(int len){
    int t1=0,t2=0,t3=0,t4=0,t5=0;
    for(int i=1; i<=len; i++){
        t1 += v[temp[i]].a;
        t2 += v[temp[i]].b;
        t3 += v[temp[i]].c;
        t4 += v[temp[i]].d;
        t5 += v[temp[i]].e;
    }
    if(t1>=c1&&t2>=c2&&t3>=c3&&t4>=c4&&money>t5){
        money = t5;
        for(int i=1; i<=len; i++){
            ans[i] = temp[i];
        }
        ans_len = len;
    }
    return;
}

void bt(int cnt, int order){
    for(int i=cnt; i<=n; i++){
        if(!ch[i]){
            ch[i] = true;
            temp[order] = i;
            calculate(order);
            bt(temp[order],order+1);
            ch[i] = false;
        }
    }
    return;
}

void input(){
    cin >> n;
    cin >> c1 >> c2 >> c3 >> c4;
    for(int i=1; i<=n; i++){
        cin >> v[i].a;
        cin >> v[i].b;
        cin >> v[i].c;
        cin >> v[i].d;
        cin >> v[i].e;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    bt(1,1);
    if(ans_len>0){
        cout << money << "\n";
        for(int i=1; i<=ans_len; i++) cout << ans[i] << " ";
        cout << "\n";
    }
    else cout << -1 << "\n";
    return 0;
}

 

이 문제의 알고리즘 분류는 문자열로 되어있다.

처음에 정답 배열을 숫자가 아닌 문자열로 저장하여 출력하는 방법을 선택했는데, 무슨 연유인지 계속해서 틀려버렸다.

반례 케이스를 찾아서 채점해봐도 모두 통과되었는데, 문자열로 할 경우 왜 틀린건지 아직까지 잘 모르겠다.

아마도 놓친 부분이 어딘가에 있었을 것이다.