알고리즘 문제/BOJ
2858번 기숙사 바닥
parkit
2019. 1. 1. 22:43
728x90
반응형
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
<첫 번째 코드, 틀린 코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #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; } | cs |
<두 번째 코드, 맞았지만, 시간은 조금 걸린다. 이중 for문>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #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; } | cs |
<세 번째 코드, 시간을 줄인 정답 코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #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; } | cs |
728x90
반응형