인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

그리고 문제의 출력 조건에서 재료의 번호를 "사전 순으로 가장 빠른 것을 출력한다." 이 부분이 제 풀이에서는 어차피 1번 재료부터 쌓아 갔으니 고려하지 않아도 되는 부분인가요??

=> 로직상 그렇게 보입니다.

그러나 sort 부분이 틀린 것 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int mp, mf, ms, mv;
int psum, fsum, ssum, vsum, csum;
vector<int> v;
vector<pair<int, vector<int>>> ret;

struct A {
    int p, f, s, v, c;
} arr[16];

void go(int idx) {
    if (psum >= mp && fsum >= mf && ssum >= ms && vsum >= mv) {
        ret.push_back({csum, v}); 
        return;
    }

    for (int i = idx; i < N; i++) {
        v.push_back(i);
        psum += arr[i].p;
        fsum += arr[i].f;
        ssum += arr[i].s;
        vsum += arr[i].v;
        csum += arr[i].c;

        go(i + 1);  
 
        v.pop_back();
        psum -= arr[i].p;
        fsum -= arr[i].f;
        ssum -= arr[i].s;
        vsum -= arr[i].v;
        csum -= arr[i].c;
    }
}

int main() {
    cin >> N;
    cin >> mp >> mf >> ms >> mv;
    for (int i = 0; i < N; i++) {
        cin >> arr[i].p >> arr[i].f >> arr[i].s >> arr[i].v >> arr[i].c;
    }

    go(0);

    if (ret.empty()) {
        cout << -1 << "\n";
    } else { 
        sort(ret.begin(), ret.end(), [](const pair<int, vector<int>>& a, const pair<int, vector<int>>& b) {
            if (a.first == b.first) return a.second < b.second;
            return a.first < b.first;
        }); 
        cout << ret[0].first << "\n";
        for (int idx : ret[0].second) {
            cout << idx + 1 << " ";
        }
        cout << "\n";
    }

    return 0;
}

이런식으로 다듬어봤습니다. 참고부탁드립니다.

(나머지 부분은 잘 짜셨어요 ㅎㅎ)

감사합니다.

안녕하세요, 인프런 AI 인턴입니다. jjs270402님.

이번 4-A(19942) 문제와 관련된 질문에 대해 도움을 드리도록 하겠습니다. 주어진 문제를 해결하기 위해 사용할 알고리즘 내부에서 어떤 부분이 문제를 일으킬 수 있는지 살펴보고자 합니다.

문제 이해 및 접근 방법

1. 조건과 구현 방식: “사전 순으로 가장 빠른 것을 출력한다”는 조건에서 사전 순 정렬은 중요합니다. 하지만 이미 재료를 1번부터 쌓아 가는 방식이라면, 이 조건은 이미 맞춰지는 상태일 수 있습니다. 그렇다면 이 측면에서 별도로 고려할 필요는 적을 수 있습니다. 하지만, 그렇게 구축되었는지 코드의 흐름을 점검하는 것이 중요합니다.

2. 디버깅 방향:

   • 조건 충족 확인: 알고리즘이 모든 조건을 올바르게 만족하는지, 특히 사전 순 정렬을 필요로 할 경우 이에 맞는지 확인이 필요합니다.
     
   • 예제 및 반례 테스트: 샘플 입력뿐 아니라, 다양한 예측되지 않은 케이스로 테스트해 보는 것도 유용합니다.
     

참고 게시글

아래 기존의 유사한 질문들이 도움될 수 있습니다. 이러한 답변을 참고하여, 문제를 해결해보세요:

• 3주차 개념 강의에서 첫 문제(연구소_14502) 질문드립니다!!
  
  • 이 질문에서는 문제와 관련된 개념적인 접근 방식을 설명하고 있습니다. 특히 완전탐색과 백트래킹을 다루고 있어 유사한 전략을 필요로 하는 문제들에 활용할 수 있습니다.
    

제가 제공한 링크들은 강의의 전체 이해를 돕고 있습니다. 알고리즘 디버깅 과정에서 문제의 근본 원인을 파악하는 데 유용할 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.