Easy is Perfect

[백준] 4307번 C/C++ 풀이 _ 개미

  • melonicedlatte
  • Feb 02, 2018


문제 : https://www.acmicpc.net/problem/4307 

개미 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB126058947548.768%

문제

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이 때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 나타낸다. 개미의 위치는 1000000보다 작거나 같으며, 공백으로 구분되어져 있다.

출력

각 테스트 케이스에 대해서, 두 숫자를 출력한다. 첫 번째 숫자는 개미가 모두 땅으로 떨어지는 가능한 시간 중 가장 빠른 시간, 두 번째 숫자는 가장 늦은 시간이다.

예제 입력 

2
10 3
2
6
7
214 7
11
12
7
13
176
23
191

예제 출력 

4 8
38 207

힌트

출처

Contest > Waterloo's local Programming Contests > 19 September, 2004 B번


- 문제를 풀다가 정답률이 48% 라서 적당한 문제라고 생각하고 들어갔는데, 생각보다 엄청나게 어려운 문제처럼 느껴졌다.
구조체 배열을 선언하고 구조체에 방향을 설정해서, 함수 안에서 지속적으로 코드를 돌려야하나? 라고 생각을 하다가 정답률로 보나 알고리즘으로 보나 그런 복잡한 코드는 아닐 것 같아서 계속 생각해봤다.
계속 생각해도 결국 답을 찾지 못하고, 충돌을 생각하니 너무 복잡했다. 

결국 구글에 검색해서 풀이를 살펴보니 굉장히 간단했다. 
최소값은 누구나 구할 수 있고, 최대값이 고민이었는데 아래의 구절이 그냥 핵심이다. 
'충돌하는 물체는 반대 방향으로 가지만, 생각해보면 똑같은 방향으로 계속 간다.'

> 정리해보자. 
최소값은 '중간을 기준으로 가장 가까운 녀석이 떨어지는 시간'이고,
최대값은 '중간을 기준으로 가장 먼 녀석이 반대편으로 가는 시간' 이라고 볼 수 있다. 

풀이는 아래와 같다. 

#include
#include
#include

using namespace std;

vector<int> vec;

int main() {
    int total_num = 0;
    int weight = 0;
    cin >> total_num;
    
    double total_length, ant_num;
    int min, max;

    for (int i = 0; i < total_num; i++) {
        // initialize
        vec.clear();
        min = -1;
        max = -1;

        cin >> total_length >> ant_num;
        
        for (int j = 0; j < ant_num; j++) {
            int sub;
            cin >> sub;
            vec.push_back(sub);
        }
        sort(vec.begin(), vec.end());

        // min getter
        for (int j = 0; j < vec.size(); j++) {
            int sub;
            if ((total_length / 2) > vec[j])
                sub = vec[j];
            else
                sub = total_length - vec[j];
    
            if (min == -1) {
                min = sub;
            }
            if (min < sub) {
                min = sub;
            }
        }

        // max getter
        for (int j = 0; j < vec.size(); j++) {
            int sub;
            if ((total_length / 2) > vec[j])
                sub = total_length - vec[j];
            else
                sub = vec[j];
    
            if (max == -1) {
                max = sub;
            }
            if (max < sub) {
                max = sub;
            }
        }
        
        cout << min << " " << max << endl;
    }
    system("pause");
    return 0;
}



Search