4-A 문제 풀이 질문있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-A

작성

484

강사님 안녕하세요,

4-A 문제에 대해 최대한 bitmask 사용하여 문제를 풀었는데,

문제 pass 를 못하여 작성한 코드 질문드립니다.

http://boj.kr/c8c4f304baa94765a7b205e181eadac7

문제 풀이 강의에서는 식재료의 index 자체를 vector<int> v 에 담는 것으로 풀이하셨는데

저는 식재료 index 정보를 담고있는 int 형 변수 자체를 최종 결과 출력까지 가져가서 켜진 bit 에 대한 index 를 출력하도록 구현했습니다.

min_price 갱신로직도,

가격이 갱신되는 경우. 그리고, 동일 가격이 발생한 경우에 식재료 index 갱신하는 경우를 case 분류하여 작성하였습니다.

bitmask 부분이 틀린 것 같지는 않는데, 8% 에서 계속 오류가 나오네요 ㅠㅠ

무엇이 틀린 것인지 감이 오질 않습니다.

c++코딩-테스트 C++코테 준비 같이 해요!

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ 답변드리려고 하니까 이해하셨군요 ㅎㅎ 훌륭하십니다.

강의 문제 풀이에서의 sort 는 vector container 에 담긴 vector<int> 에 대해 sort 가 진행된 것인데요.

vector<int> {1,4} // vector<int> {1,2,8} 를 비교하는 상황에서는
container size 와 관계 없이 앞쪽에 있는 요소부터 순차적으로 비교하여 판단하는 것 인가요?
즉, 1과 1에 대해서는 동일하니까 4와 2를 비교했더니 2가 더 작으니 {1,2,8} 이 더 작다고 판단한 것일까요?

>> 네 맞습니다. size와는 관계없이 판단합니다.

Kyoung Jun Kim

질문자

강사님 안녕하세요~

스스로 좀 더 생각해보다가 무엇이 틀렸는지 확인하였습니다.
그리고 그 아래 추가 질문이 있습니다.

--- 기존 코드의 문제점 ---

기존에 최소 비용 식재료 조합을 integer 변수 하나에 (bitmask) 방식으로 전달하여 sort 까지 수행하였는데 이 경우 sort 에서 문제가 발생하게 되네요

아래와 같은 2가지 동일 비용의 case 가 있다고 가정하면
-정수 5 = 0101 (식재료 1 4)
-정수 11 = 1011 (식재료 1 2 8)
정수 기준 오름차순 정렬시 5가 11보다 앞쪽에 오게 되는데,
문제에서 요구하는 사전순으로 볼때는 1,2,8 의 경우가 더 앞쪽에 오게 되는 것이더라구요.

개선 코드 : http://boj.kr/65b1b424a30e4d468c5a5ccf54b1f794

--- 추가 질문 ---

강의 문제 풀이에서의 sort 는 vector container 에 담긴 vector<int> 에 대해 sort 가 진행된 것인데요.

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

4-A 문제 풀이 질문있습니다.