문제
4행 격자에 1부터 순서대로 세로로 채워넣을 때, 두 수의 위치 사이의 맨해튼 거리를 구하라.
입력
두 자연수가 공백으로 구분되어 주어진다.
출력
두 수의 위치 간 맨해튼 거리를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 13 | 3 |
풀이
각 수의 행과 열 좌표를 구한 뒤 맨해튼 거리를 계산한다.
- 각 수를 0-인덱스로 변환한다 (n-1)
- 행은 4로 나눈 나머지, 열은 4로 나눈 몫이다
- 두 수의 행 차이와 열 차이의 절대값 합이 맨해튼 거리이다
핵심 아이디어: 4행 격자에서 수 n의 위치는 행 (n-1)%4, 열 (n-1)//4로 O(1)에 계산된다.
코드
a,b=map(int,input().split())
a-=1;b-=1
print(abs(a//4-b//4)+abs(a%4-b%4))복잡도
- 시간: O(1)
- 공간: O(1)