문제
M×N 격자를 나선형으로 순회할 때 방향을 전환하는 횟수를 구하라.
입력
M과 N이 공백으로 주어진다.
출력
방향 전환 횟수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 3 | 4 |
풀이
나선형 순회의 방향 전환 횟수를 수학 공식으로 계산한다.
- 나선형 순회에서 짧은 변의 길이가 순회 깊이를 결정한다
min(M, N)을 기준으로 기본 전환 횟수는2 * min(M, N) - 1이다- 짧은 변이 M 이하(행)인 경우 마지막 전환이 하나 줄어 1을 추가로 뺀다
핵심 아이디어: 나선형 순회의 방향 전환은 짧은 변의 길이에 의해 결정되며, 시뮬레이션 없이 O(1) 공식으로 계산할 수 있다.
코드
m, n = map(int, input().split())
print(2 * min(m, n) - 1 - (m <= n))복잡도
- 시간: O(1) — 수학 공식 계산
- 공간: O(1) — 상수 변수만 사용