백준 1074번 Z

문제 링크입니다: https://www.acmicpc.net/problem/1074

 

백준 14956번 Philosopher's Walk(https://www.acmicpc.net/problem/14956)의 쉬운 버전이었습니다.

똑같이 재귀를 이용해야하지만 해당 문제는 모든 사분면이 규칙적인 반면 힐버트 곡선(Hilbert Curve)의 경우 1, 2사분면과 3, 4사분면이 다르기 때문에 상당히 고난이도 문제였습니다.(그래서 아직까지도 못 풀고 있는 문제입니다... BaaaaaaaaaaaaaaaaaaaaaaarkingDog님한테 블로그 댓글을 통해 설명을 듣긴 했지만 구현은 여전히 못하는 상태입니다...ㅠ)

 

알고리즘은 아래와 같습니다.

1. 2 * 2 모양으로 계속 쪼개나갑니다.(1->2->3->4사분면 순으로)

2. 전역변수로 선언한 cnt를 1씩 추가하면서 해당 2 * 2 모양에 좌표가 있는지 확인합니다.

i) (R, C)를 찾았다면 cnt 출력

ii) 해당 2 * 2 모양에서 (R, C) 못 찾았다면 return

 

[수정 2021.04.01] 기존 소스는 데이터가 추가됨에 따라 시간 초과가 발생해 새로 코드를 작성해서 포스팅합니다. 알고리즘은 같지만 기존 소스와 달리 1, 2, 3, 4분면 위치에 따라 계산을 미리한 뒤 재귀호출을 하여 실행속도가 많이 빨라졌습니다!

 

기존소스

 

수정된 소스

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~