[Python] 백준 1074번 : Z

문제

1074번: Z

[ 문제 조건 ]

• Z 모양 순서대로 방문
• 입력한 r행 c열이 몇번 째로 방문하는지 출력

[ 해결순서 ]

• 1번째 풀이 -> 실패
  1. 재귀적으로 모든 분면의 모든 값을 확인해서
  2. 2X2 배열일 때 ( 더이상 등분하지 않아도 되면 )
  3. 조건에 맞을 때까지 값을 하나씩 늘려가면서 몇번째 방문인지 계산하다가
  4. r행 c열의 조건이면 여태껏 더한 방문값을 출력하고 종료한다.
  5. 이렇게 하면 시간 초과가 날 뿐만 아니라, 입력한 값에 포함하는 분면이 아닌 값들도 모두 확인해 비효율적인다.
• 2번째 풀이 (참고)
  1. 이 풀이는 아이디어를 참고한 후 코드를 짜면서 해석했는데, 이 문제를 풀 때 내가 처음에 생각해낸 아이디어와 비슷했다. (코드를 못 짜겠어서 1번째 풀이로 풀었지만..)
  2. 입력한 값이 몇 사분면인지 계산한 후, 예를 들어 3사분면에 속해있다면 1,2 사분면의 값들을 확인하지 않고 방문횟수만 더해줘도 방문처리가 된다.
  3. 그리고 시작점을 2^N X 2^N 배열의 중간값을 빼면 (12, 15, 18~19줄)
  4. n==1이 되었을 때(2 X 2 배열일 때) 시작점 0,0을 기준으로 입력한 값이 어디에 있는지 방문값을 맞게 더한다음에 출력하면 최종 값이 된다.

✏️한줄평

: 분할정복 문제를 저번에 풀었을 때도 1번풀이처럼 모든 경우의 수를 구한 다음에 값을 찾으면 그때 종료하고 출력하는 식으로 해결했는데, 비효율적인건 알고있었으나 시간초과가 날 수도 있는 문제가 있다는 것을 느꼈다. 그만큼 시간도 오래걸리고 메모리도 많이 차지할 테니 좀 더 효율적으로 코드를 짜는 방법을 공부해야겠다.

---

코드

1번째 풀이

2번째 풀이