[Softeer] 금고털이(Lv.2) - Day2

📋 개요

 

2024.01.26 - [Algorithm/Problem] - [Softteer] A+B(Lv.1) - 1Day

2024.01.26 - [Algorithm/Problem] - [Softteer] 근무 시간(Lv.1) - 1Day

[Softteer] 근무 시간(Lv.1) - Day1

[Softteer] A+B(Lv.1) - 1Day

 

1일차에 이어서 2일차도 진행했다. 2일차에는 Lv2 2문제가 있었다.

첫번째 문제는 살펴볼 금고털이 문제였다.

 

자주 등장하는 문제 유형으로 힌트는 그리디 알고리즘이다~

 

https://softeer.ai/practice/6288

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

🧩 문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

⛔ 제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

📝  형식 

📥 입력	📤 출력
첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.	첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

💡  예제

🔢 번호	📥 입력	📤 출력
1	100 1 90 1 70 2	170

🖥️ 내 코드

---

📖  해설 및 느낀점

새롭게 활용한 자료구조 형이 있었다. pair라는 키워드의 자료구조인데, 자바나 다른언어에서는 볼수 없던 자료구조라 생소했지만, 사용한 이유는 다른분들이 작성하신 C++ 코드를 리뷰하면서 자주 나오던 키워드였던거 같다.

2024.01.26 - [Language/C++] - [C++] STL(Standard Template Library) - Pair(페어)

vector< pair<int,int> > metal; //pair안에 vector로 감싼 구조

//pair로 만들어서 vector에 밀어넣기
metal.push_back(make_pair(P,M));
 
//오름차순 정렬
sort(metal.begin(),metal.end());

 

대게 pair라는 키워드는 데이터가 한쌍으로 있을때 사용하는 것 같다.

 

또한, 이 문제의 풀이는 Greedy Algorithm이다. 

최적해를 구하는 데에 사용되는 근사적인 방법을 그리디 알고리즘이라고 한다. 비슷한 문제로는 최소한의 동전갯수로 거스름돈 거슬러주기와 같은 문제들이 있다.

결국, 문제에서 요구하는 바는 담을때 가장 비싼거를 먼저 담아야한다는 점을 유의하면서 풀어야한다. 그게 비싼돈을 받는게 이 문제에서 최적의 해이기 때문이다. 

 

사실 C++ 코드를 잘 작성하고 있는지는 모르겠다...최대한 인덴트랑 그나마 인터넷 뒤져봐서 찾은 컨벤션?이라고 해야하나... 그런 것들을 맞춰보려고 했지만 작성하다보니 JAVA느낌으로 뭔가 작성하는거 같은 느낌이 들기도 하고... 고수님들의 많은 피드백 부탁드립니다!