[11320번] 삼각 무늬 - 1

문제 출처 :

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을 해준다.

이 방법을 토대로  

[11312번] 삼각 무늬 - 2 :: https://www.acmicpc.net/problem/11312

문제도 해결해보자.

소스 코드 : 

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