2858번 기숙사 바닥

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

문제를 읽어보고, 엄청 쉬운 문제인 줄 알았다.

문제에서도 항상 정답이 유일한 경우에만 주어진다고 하여서, 

단순히 첫 번째 코드처럼 곱셈을 하여, 갈색과 빨간색의 합과 같은지만 비교하였다.

하지만 생각해보니, 

구한 가로와 세로의 길이를 활용해 입력한 갈색과 빨간색의 개수까지 같은지 비교했었야 했다.

여하튼, 이렇게 해서 두 번째 코드(이중 for문)까지 작성하여 제출했고, 맞았지만 시간이 남들보다 더 걸렸다.

그래서, 구글링을 해보니, 다른 분들은 세 번째 코드처럼 for문을 하나만 썼었다.

좀 더 생각을 해보고, 문제도 잘 읽어야겠다.

참고로, 

갈색의 개수는 (가로 - 2) * (세로 - 2) 이다.

아래 그림을 보면서 생각해보자.

혹시 몰라서 테스트 케이스도 남긴다.(윗 줄이 입력, 아래가 출력 결과이다.)

12 4

4 4

24 25

7 7

3988 992016

998 998

3004 2996

1500 4

4008 9985

1999 7

2662 338198

988 345

4796 1275204

1600 800

4004 999999

1003 1001

4570 1253960

1365 922

4860 1473472

1234 1198

24 24

8 6

<첫 번째 코드, 틀린 코드>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void)
{
    long long R = 0, B = 0;
 
    scanf("%lld %lld", &R, &B);
 
    long long sum = R + B;
 
    for (long long i = 3; i <= sum / 2; i++)
    {
        for (long long j = 3; j <= sum / 2; j++)
        {
            if (i < j) continue;
 
            if (sum == i*j)
            {
                printf("%lld %lld\n", i, j);
 
                return 0;
            }
        }
    }
 
    return 0;
}
 

<두 번째 코드, 맞았지만, 시간은 조금 걸린다. 이중 for문>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void)
{
    long long R = 0, B = 0;
 
    scanf("%lld %lld", &R, &B);
 
    long long sum = R + B;
 
    for (long long i = 3; i <= sum / 2; i++)
    {
        for (long long j = 3; j <= sum / 2; j++)
        {
            if (i < j) continue;
 
            if (sum == i*j)
            {
                long long brown = (i - 2)*(j - 2);
                long long red = sum - brown;
 
                if (red == R && brown == B)
                {
                    printf("%lld %lld\n", i, j);
 
                    return 0;
                }
            }
        }
    }
 
    return 0;
}

<세 번째 코드, 시간을 줄인 정답 코드>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void)
{
    long long R = 0, B = 0;
 
    scanf("%lld %lld", &R, &B);
 
    long long sum = R + B;
 
    for (long long i = 3; i <= sum / 2; i++)
    {
        if (i < sum / i) continue;
        
        if (sum % i == 0)
        {
            long long j = sum / i;
 
            long long b = (i - 2) * (j - 2);
 
            long long r = sum - b;
 
            if (b == B && r == R)
            {
                printf("%lld %lld\n", i, j);
 
                return 0;
            }
        }
    }
 
    return 0;
}