[윈터코딩] 멀쩡한 사각형

programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

생각보다 간단한 문제였는데 고민을 오래했다.

 

*실패한 방법

O(n^2) 풀이법

1, 왼쪽 상단에서 오른쪽 하단으로 이어지는 대각선을 생각하였다.(어차피 대칭이므로 어느 선을 그어도 동일)

2, 정사각형의 왼쪽 하단과 오른쪽 상단의 점을 구한 후 두 점이 대각선의 아래에 있나 위에 있나 판별하여 갯수를 세어줌

=> 결론은 시간초과와 약간의 실패 기록들이 떴다. 따라서, 다른 방법을 생각해 보았다

 

O(n)풀이법

1, 생각을 해 보니 한 직각삼각형에서 정사각형 갯수를 구하면 대칭이므로 2배를 해 주면 되는 계산이였다.

2, 나는 좌측 아래에 있는 직각삼각형을 고려하였는데 각 열마다 위로 올라가면서 직선과 만나지 않는 사각형의 갯수는 직선이 좌측 상단에서 우측 하단에서 떨어짐으로 해당 열의 +1 에 해당하는 부분에서 직선이 걸쳐지는 행의 위치를 구한 다음 그 밑 부분을 다 포함을 시켜주면 되었다. 따라서 행만 순회를 함으로 O(n)으로 계산이 가능하다.

 

소스코드

using namespace std;

long long solution(int w, int h){
    long long answer = 0;

    double a = ((double)-h/(double)w);
    int b = h;
    int aim;

    for(int i = 0 ; i < w-1; i++){
        int aim  = a*(i+1) + b;
        answer += aim;
    }
    return answer * 2;
}