매번 코테를 보고 나면은 내가 부족한점 + 집중해야 되는 부분을 조금씩 알게 되는데 최근에 코테를 보고 나서는 Greedy 분야랑 DP 분야를 더 공부하기로 마음 먹었다. 현재 내 상태로 DFS/BFS + Simulation + Matrix 류의 문제들은 꽤 자신이 있는 상태이기 때문에 쉽게 나올 수도 있는 Greedy 와 DP 분야를 더 집중해봐야겠다.
이번에 풀어봤던 문제는 "배" 라는 문제이고 박스를 특정 무게만 담을 수 있는 크레인과 박스의 무게가 주어졌을때 배로 옮길 수 있는 최소한의 움직임을 출력하면 되는 문제이다.
그리디한 접근법으로 무게를 담을 수 있는 크레인을 가장 튼튼한것 부터 시작해서 가장 무거운 물건들을 담으면 된다고 생각했다. 그런데 이 문제는 구현이 조금 어려웠는데 그냥 단순하게 정렬된 상태의 마지막 크레인부터 두번의 loop를 날리면서 모든 box 를 확인한다면은 시간초과가 나온다.
그리디 유형의 문제들은 항상 최적화된 선택과 그 선택을 받침할 수 있는 아이디어도 중요한거 같다. 물론 이 패턴은 분명 문제를 많이 풀다보면 느낄거라고 생각한다. 가장 처음에는 배열을 만들어가지고 각 크레인이 담을 수 있는 무게들의 갯수를 저장 해주었다. 후에는 각 크레인을 while(true) 만큼 돌리면서 크레인이 옮길 수 있는 숫자를 하나씩 줄여주었다.
그리고 줄인 숫자가 박스의 숫자와 같다면 모든 박스를 옮긴거기 떄문에 바로 답을 반환해주었다.
#include <iostream>
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100010
using namespace std;
int N;
vector<int> cranes;
int M;
vector<int> boxes;
vector<int> check;
void Input(){
cin >> N;
check.resize(N);
for(int i = 0; i < N; i++){
int a;
cin >> a;
cranes.push_back(a);
}
cin >> M;
for(int i = 0; i < M; i++){
int a;
cin >> a;
boxes.push_back(a);
}
}
void Solution(){
sort(cranes.begin(),cranes.end());
sort(boxes.begin(),boxes.end());
int answer = 0, index = 0, cnt = 0;
if(cranes.back() < boxes.back()){
cout << -1;
return;
}
for(int i = 0; i < boxes.size(); i++){
if(cranes[index] >= boxes[i]) check[index]++;
else{
index++;
i--;
}
}
while(true){
for(int i = cranes.size()-1; i >= 0; i--){
for(int j = i; j >= 0; j--){
if(check[j]){
check[j]--;
cnt++;
break;
}
}
}
answer++;
if(cnt == boxes.size()) break;
}
cout << answer;
}
void Solve(){
Input();
Solution();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("input.txt", "r", stdin);
Solve();
return 0;
}배운점:
1. Greedy 한 접근법
2. 배열을 따로 저장해주어 최적화 해주기
