13335 - c++

문제 이해는 완벽하게 하였으나 구현이 쉽지 않았다....

 

---

요약

1. 다리가 버틸 수 있는 최대 하중을 알고 있으니 어떻게 하면 최소한으로 트럭을 이동할 수 있는가

 

---

첫 아이디어

1. 자료구조 큐를 사용하고, 트럭이 다리위에 올라갈 때마다 추가한다.

2. 트럭이 다리위에서 나가면 총 무게 - 큐.front() 를 빼주는 식으로 무게를 계산하려 했다.

 

코드

int n, w, l;
int total = 0, cur = 0;
int truck[1001];
int cnt = 0;
queue<int> bridge;

int main()
{
  init();
  cin >> n >> w >> l;
  for(int i =0; i < n; ++i)cin >> truck[i];
  while(cur != n){//문제점
    for(int i=0; i < w; ++i){
      ++cnt;
      while(total < l){
        int nxtot = total + truck[cur];
        if(n!=cur && nxtot <= l){
          bridge.push(truck[cur++]);
          total = nxtot;
        }
        else break;
      }
    }
    if(!bridge.empty()){
      total -= bridge.front();
      bridge.pop();
    }
  }
  cout << cnt;
  return 0;
}

이렇게 코드를 노트에 적으면서 설계 했는데 틀렸다는 걸 코드를 에디터에 적고 알았다.......

 

위 코드의 문제점은 무엇인가

트럭이 브릿지에 잘 들어오고 나갔을 때 무게를 잘 빼준다. 하지만 첫 번째 트럭이 나가는 순간 종료된다....

그러므로 뒤 트럭은 계산을 하지 못하게 된다...

---

두 번째 아이디어

1. 가장 앞에있는 트럭의 인덱스를 저장하면서 연산한다.

2. 큐에는 무게와 전 트럭사이의 거리를 저장하려 했다.

 

이건 구현하지 못하고 너무 복잡해 질것 같아서 멈췄다.

---

정답을 보고

답을 봤다.

int n, w, l;
int cnt = 0;
int bridge[101] = {0,};
queue<int> truck;

void go(){
  for(int i = w-1; i > 0; --i)bridge[i] = bridge[i-1];
  bridge[0] = 0;
}

bool isEmpty(){
  for(int i =0; i < w; ++i){
    if(bridge[i])return false;
  }
  return true;
}

int weight(){
  int c = 0;
  for(int i =0; i < w; ++i)c += bridge[i];
  return c;
}

int main()
{
  init();
  cin >> n >> w >> l;
  while(n--){
    int num;
    cin >> num;
    truck.push(num);
  }
  do{
    int tmp = weight();
    if(tmp <= l){
      tmp -= bridge[w-1];
      go();
      cnt++;
      if(!truck.empty() && tmp+truck.front() <= l){
        bridge[0] = truck.front(); truck.pop();
      }
    }
  }while(!isEmpty());
  cout << cnt;
  return 0;
}

진짜 생각도 못한 방법 이였다. do while을 쓸 생각을 못했다. 

어떻게 이런 생각을 한 걸까, 어떻게 이런 결론에 도달한 걸까

bridge를 그러니 다리 위의 트럭을 놓을 생각을 왜 못했을까

---

여기서 어떤 것을 얻었는가

1. 많은 연산이 필요할 것 같다고 겁먹고 시도하지 않은 나의 쓰레기 같은 마인드를 버린다.

2. do while문을 사용하는 것, 무조건 처음에 실행해야 할 때 do while문 사용을 고려해 봐야겠다.