2015136077   3년 전

4중 for문을 통해 구현을 해서 시간초과가 날 수도 있단 생각은 들었지만 연산 자체가 필수 불가결한 부분이라 더 줄일 수 있는 방법을 못찾겠네요 ㅠ

방식은 다음과 같습니다

2차원 벡터에 삼각형의 값을 저장합니다 (triangle)

2차원 bool 벡터에 해당 인덱스의 단위삼각형이 정삼각형인지, 역삼각형인지 저장합니다.(triangle_ok)

단위 삼각형을 모두 방문하면서 (2중 for문 i,j)

 -> 단위 삼각형(i,j)를 기준으로  만들 수 있는 삼각형을 모두 찾습니다. (2중 for문 a,b)

    예를 들면 예제에서 

    1. 맨 위의 단위 삼각형(i,j)를 (a,b)로 초기화하여 6을 확인하고,

    2. 그 다음 6, -24, 0, 12를 확인하고, 

    3.그 다음 6, -24, 0, 12 , -10, 12, 40, -4, 6을 확인하고,

   4. 다음 번을 확인했더니 인덱스가 초과되면 종료

여기서 더 줄일 수 있나요?

4중 for문을 통해 구현하긴 했지만 단위 삼각형을 모두 방문해야하고(2중 for문 i,j), 그 다음 방문한 단위 삼각형을 기준으로 만들수 있는 거대 삼각형 (2중 for문 a,b)를 탐색해야 할 텐데 이 방식보다 덜 계산하는 방식은 상식적으로 찾을 수 없습니다.

백준님의 강의해답에서도 2중 for문에 재귀적인 방식으로 접근해서 결국엔 4중 for문과 마찬가지의 복잡도를 가지는걸로 확인했습니다.

더 줄일 수 있는 부분이 있나요?

댓글을 작성하려면 로그인해야 합니다.