반응형
문제 출처 :
https://www.acmicpc.net/problem/11320
알고리즘 분석 :
문제 해결에 필요한 사항
1. 수학
생각해보면 생각외로 간단하다.
a와 b 삼각형을 모두 1*1로 삼각형으로 바꾸어 준다.
예를 들어
한변의 길이가 2인 정삼각형은 총 4개의 1*1삼각형이 나올 것이다.
한변의 길이가 3인 정삼각형은 총 9개의 1*1삼각형이 나올 것이다.
한변의 길이가 4인 정삼각형은 총 16개의 1*1삼각형이 나올 것이다.
...
한변의 길이가 n인 정삼각형은 총 n*n개의 1*1삼각형이 나올 것이다.
이제 1*1로 분리된 a와 b삼각형의 개수를 a1, b1이라 하자.
b를 a로 덮어야하는데 이때 a1 / b1이 완벽하게 덮기위한 필요한 수이다.
만약 a1 % b1 즉, 완벽하게 덮었다 생각했는데 나머지가 있다면 덜 덮혔다는 뜻이되고, 이때는 정답에 +1을 해준다.
이 방법을 토대로
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 | #include <iostream> #include <cstdio> using namespace std; int main() { int tc; scanf("%d", &tc); while (tc--) { int a, b; scanf("%d %d", &a, &b); int a1 = a*a; int b1 = b*b; int ans = a1 / b1; if (a1 % b1) ans++; cout << ans << endl; } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[3184번] 양 (0) | 2017.09.24 |
---|---|
[11313번] Best Buddies (0) | 2017.09.23 |
[2810번] 컵홀더 (0) | 2017.09.21 |
[11292번] 키 큰 사람 (0) | 2017.09.19 |
[6416번] 트리인가? (0) | 2017.09.18 |