algorithm shoemaker problem

• 문제보기
• 4장 Summit Pages

Mastojun

• 이것도 풀어봤던 문제이긴한데, 도무지 어떻게 풀었는지 떠오르지 않아서 무지 애먹었습니다. 머리가 퇴화한 기분을 느꼈다능...

이 문제 풀면서 발견한 Programming-Challenges로봇의 문제점

    copy(Data.begin(), Data.end(),ostream_iterator<SData>(cout, " "));

위코드는 컴파일 에러입니다. 컴파일 에러 내용은 아래와 같습니다.

    pgdaemon.tmp.cpp: In function 'int main()':
    pgdaemon.tmp.cpp:55: error: 'ostream_iterator' was not declared in this scope
    pgdaemon.tmp.cpp:55: error: expected primary-expression before '>' token

ostreamiterator가 선언하지 않았다고해서 헤더파일 문제인지 일았는데 여러가지 삽질끝에..

    copy(Data.begin(), Data.end(),ostream_iterator<struct SData>(cout, " "));

• 위와 같이 수정을 했더니 정상적인 컴파일이 되었습니다.

• 하지만 오랫동안 애썻는데도 불구하고 각 줄마다 마지막에 ' ' 가 하나 더 들어가서 PE(Presentation error)가 발생하더군요 :D

• vector는 제대로 되었는데 ostreamiterator만 안되는게 특별한 이유라도 있을까요? 아니면 단순히 G++이나 홈페이지의 문제일까요?

문제 풀이 코드

    #include <iostream>
    #include <vector>
    #include <iterator>
    #include <algorithm>
    
    using namespace std;
    
    struct SData
    {
    	int T;
    	int S;
    	int n;
    
    	bool operator<(const SData &rhs) const
    	{
    		return rhs.T*S > rhs.S*T;
    	}
    
    };
    
    vector<SData> Data;
    
    void InputData()
    {
    	int n;
    	SData TempData;
    	Data.clear();
    
    	cin >> n;
    
    	for(int i = 1; i <= n; ++i )
    	{
    		cin >> TempData.T >> TempData.S;
    		TempData.n = i;
    
    		Data.push_back(TempData);
    	}		
    }
    
    void OutputData()
    {
    	for(int i = 0; i < Data.size(); ++i )
    	{
    		cout << Data[i].n;
    		if( i != Data.size()-1 ) cout << " ";
    	}
    }
    
    int main()
    {
    	
    	int n;
    
    	cin >> n;
    	while(n--)
    	{
    		InputData();
    		sort(Data.begin(), Data.end());
    		OutputData();
    		cout << endl;
    
    		if(n) cout << endl;
    	}
    
    	return 0;
    }

CynicJJ

풀이

1. 패널티가 클수록 빨리 처리하는것이 유리
2. 작업일 수가 적을수록 빨리 처리하는 것이 유리
3. 그렇다면 (패널티/작업일) 순으로 처리하는것이 유리???
4. (패널티/작업일)이 같은 경우 순서를 바꿔도 총 패널티에는 변화 없다

어려움

1. 그럴싸하지만 뭔가 꺼림칙하다

실패한 풀이

1. 이 일을 진행 할 경우 발생하는 패널티의 총합이 적은 것 부터 처리
2. 패널티의 총합은 이 일에 필요한 시간에 다른 일들의 패널티를 곱한것들의 합
3. 샘플 안 풀림
4. 풀이대로라면 2 1 3 4 가 아니라 2 3 1 4 가 된다