[백준/C++] 11880번: 개미

문제 & 링크

https://www.acmicpc.net/problem/11880

 

풀이

!! 범위를 고려하여 long long int 자료형을 사용하여야 함!!

1.  개미가 이동한 최단 거리는 (세로 + 높이)와 가로를 두 변으로 하는 빗변이기에 가로의 길이가 제일 길어야 한다. 

* 세로 or 높이가 가장 길 경우 개미가 이동한 경로는 최단 거리가 아니게 되므로 모순이 된다.

2. algorithm 헤더 파일의 max 함수를 이용하여 세 값 중 가장 큰 값(가로)을 저장한다.

3. if 문을 사용하여 가장 큰 값(가로)이 아닌 두 값(세로, 높이)의 합을 저장한다.

4. 2와 3을 이용하여 거리의 제곱을 출력한다.

 

이슈

알고리즘에 문제가 없는데도 시간 초과가 지속적으로 발생했다.

 

해결

코딩테스트에 한정하여 프로그램의 실행 속도를 높일 수 있는 세 가지 방법에 대해서 배우게 되었다.

 

1.  ios::sync_with_stdio(false);

- C++ 표준 스트림은 디폴트로 C 표준 스트림과 동기화되어 있다. 이 코드를 이용하여 비동기화하면 C++ 표준 스트림이 독립적으로 작동하여 더 빠르게 실행된다.

2. cin.tie(NULL);

- cin은 디폴트로 cout와 연결되어 있어 cin이 호출될 때 마다 자동으로 cout이 플러시된다. 이때 플러시란 출력 버퍼를 강제로 비우는 작업이다. 이 코드를 이용하여 연결을 비활성화하면 불필요한 플러시를 하지 않아 입출력 성능이 향상된다.

3. "\n";

- endl은 줄바꿈("\n")과 함께 cout을 플러시하는 역할을 한다. 따라서 줄바꿈만 하는 이 코드를 이용하면 불필요한 플러시를 하지 않아 입출력 성능이 향상된다.

 

이 세 가지 방법을 사용하여 시간 초과 문제를 해결하였다.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;

    cin >> T;

    long long a, b, c, max_abc, sum;
    for (int i = 0; i < T; i++) {
        cin >> a >> b >> c;
        max_abc = max({a, b, c});
        
        if (max_abc == a) {
            sum = b + c;
        }
        else if (max_abc == b) {
            sum = a + c;
        }
        else {
            sum = a + b;
        }
        
        cout << max_abc * max_abc + sum * sum << "\n";
    }

    return 0;
}