https://www.acmicpc.net/problem/13335
풀고보면 간단한 거 같은데
첫 시도에는 왜였을까..
4시간동안 시도했는데도 안되서 포기했었다.
그래서 이 문제는 이제 쳐다도 보기 싫은데,
이걸 안풀고 넘어가자니 백준만 생각하면 힘이 빠져서 오늘 다시 시도해봤다.
그리고 얼마전에 '알고리즘 문제 해결 전략'이라는 책 초반 부분을 읽으면서
아래 사진과 같은 6단계 문제 해결 전략을 알 수 있었다.
그래서 이번에 문제 풀 때는 반드시,,! 계획 먼저 세우겠다고 다짐했다 ㅠ
처음 풀 때에는 빨리 풀 생각에 급해서 계획을 뜬 구름 잡듯 했던 것 같다.
그렇게 해서 세운 계획..? 알고리즘..? 시뮬레이션>?!
이렇게 하고 나니까 코드도 예전보다 깔끔해져서 여태 짠 것 중에 가장 맘에 들었다.
아직 이런 걸로 만족하면 안되지만 ㅎㅎ
깔끔한 코드로 한 걸음 나아갔다고 생각한다..!
아,,!
이제 이론상 거의 다 됐다고 생각했고,
예제도 잘 출력되는데 '틀렸습니다'가 나왔다.
이 때 디버깅하기가 참 막막한데,,
백준 질문 탭에서 반례를 찾아서 해보니까 하나가 무한루프 도는 케이스를 찾을 수 있었다!
아직 다리위에 있는 트럭이 아니고, 트럭이 올라갈 수 있는 상황도 아니면,
break를 해주어야 했다.
입력
5 2 10
9 4 8 1 5
출력
9
안그러면 위의 케이스에서 9가 다리위에 있을 때,
4랑 8은 올라갈 수 있는 상황이 안되니까
반복문이 1까지 가서 4, 8을 건너뛰고 1을 다리위에 올리더라.
이번 문제를 통해 얻은 교훈은
1. 제발 계획
2. 예제가 다 출력되는데 '틀렸습니다'가 나오면 반례를 찾아보자!
< 전체 CODE >
#include <iostream>
using namespace std;
// 교훈: 반례찾기
class Bridge
{
public:
int cur_weight;
int max_weight;
int length;
int cur_truckNum;
public:
Bridge()
{
cur_weight = 0;
max_weight = 0;
length = 0;
cur_truckNum = 0;
}
};
class Truck
{
public:
int weight;
int move_distance;
bool isOnBridge;
public:
Truck()
{
weight = 0;
move_distance = 0;
isOnBridge = false;
}
};
int main(void)
{
int n = 0, w = 0, L = 0;
cin>>n>>w>>L;
Bridge bridge;
bridge.length = w;
bridge.max_weight = L;
Truck trucks[n];
for(int i=0; i<n; i++)
{
cin>>trucks[i].weight;
}
int startIdx = 0;
int time = 0;
while(trucks[n-1].move_distance <= bridge.length)
{
time++;
for(int i = startIdx; i<n; i++)
{
if(!trucks[i].isOnBridge)
{
if(trucks[i].weight + bridge.cur_weight <= bridge.max_weight
&& bridge.cur_truckNum < bridge.length)
{
trucks[i].isOnBridge = true;
trucks[i].move_distance += 1;
bridge.cur_weight += trucks[i].weight;
bridge.cur_truckNum += 1;
break;
}
else
{
break;
}
}
else
{
trucks[i].move_distance += 1;
if(trucks[i].move_distance > bridge.length)
{
startIdx++;
trucks[i].isOnBridge = false;
bridge.cur_weight -= trucks[i].weight;
bridge.cur_truckNum -= 1;
}
}
}
}
cout<<time<<endl;
return 0;
}