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

Question

강사님 안녕하세요, 4-A 문제에 대해 최대한 bitmask 사용하여 문제를 풀었는데, 문제 pass 를 못하여 작성한 코드 질문드립니다. http://boj.kr/c8c4f304baa94765a7b205e181eadac7 문제 풀이 강의에서는 식재료의 index 자체를 vector<int> v 에 담는 것으로 풀이하셨는데 저는 식재료 index 정보를 담고있는 int 형 변수 자체를 최종 결과 출력까지 가져가서 켜진 bit 에 대한 index 를 출력하도록 구현했습니다. min_price 갱신로직도, 가격이 갱신되는 경우. 그리고, 동일 가격이 발생한 경우에 식재료 index 갱신하는 경우를 case 분류하여 작성하였습니다. bitmask 부분이 틀린 것 같지는 않는데, 8% 에서 계속 오류가 나오네요 ㅠㅠ 무엇이 틀린 것인지 감이 오질 않습니다.

kundol · Answer

안녕하세요 ㅎㅎ 답변드리려고 하니까 이해하셨군요 ㅎㅎ 훌륭하십니다. 강의 문제 풀이에서의 sort 는 vector container 에 담긴 vector 에 대해 sort 가 진행된 것인데요. vector {1,4} // vector {1,2,8} 를 비교하는 상황에서는 container size 와 관계 없이 앞쪽에 있는 요소부터 순차적으로 비교하여 판단하는 것 인가요? 즉, 1과 1에 대해서는 동일하니까 4와 2를 비교했더니 2가 더 작으니 {1,2,8} 이 더 작다고 판단한 것일까요? >> 네 맞습니다. size와는 관계없이 판단합니다.

Kyoung Jun Kim · Answer

강사님 안녕하세요~ 스스로 좀 더 생각해보다가 무엇이 틀렸는지 확인하였습니다. 그리고 그 아래 추가 질문이 있습니다. --- 기존 코드의 문제점 --- 기존에 최소 비용 식재료 조합을 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 에 대해 sort 가 진행된 것인데요. vector {1,4} // vector {1,2,8} 를 비교하는 상황에서는 container size 와 관계 없이 앞쪽에 있는 요소부터 순차적으로 비교하여 판단하는 것 인가요? 즉, 1과 1에 대해서는 동일하니까 4와 2를 비교했더니 2가 더 작으니 {1,2,8} 이 더 작다고 판단한 것일까요?