문제 링크: https://www.acmicpc.net/problem/1952
1. 공식 도출 과정
1.1 기본 개념 정의
달팽이 경로에서 **레이어(layer)**란 표의 가장자리부터 안쪽으로 들어가는 동심원 형태의 고리를 의미합니다.
$k = \min(M, N) \text{ (총 레이어 수)}$
1.2 표를 이용한 레이어 시각화
5×4 표에서의 레이어 구조:
┌─────────────────────────────────────┐
│ Layer 1 (외곽) │
│ → → → → (4칸, 꺾임없음) │
│ ↓ ↓ │
│ ↓ ↓ │
│ ↓ ↓ │
│ ← ← ← ← ← (5칸, 1회 꺾임) │
│ ↗ │
│ ↑ Layer 2 ↑ (3칸, 1회 꺾임) │
│ └──────────────┘ │
└─────────────────────────────────────┘
Layer 1: 외곽 (4→ + 3↓ + 4← + 2↑) = 13칸, 2회 꺾임
Layer 2: 내부 (2→ + 1↓ + 2← + 0↑) = 5칸, 1회 꺾임
Layer 3: 중심 (2→) = 2칸, 0회 꺾임
레이어별 꺾임 패턴 분석:
| 레이어 크기 | 완전한 사각형? | 꺾임 횟수 | 설명 | |
| 1 | 5×4 | ✓ (완전) | 2회 | 오른쪽 끝→아래, 아래 끝→왼쪽 |
| 2 | 3×4 | ✓ (완전) | 2회 | 오른쪽 끝→아래, 아래 끝→왼쪽 |
1.3 단계별 수식 도출
Step 1: 레이어 수 정의
M×N 표에서 가능한 레이어 수는 짧은 변의 절반으로 결정됩니다.
$k = \min(M, N)$
Step 2: 완전 레이어와 불완전 레이어 구분
레이어 $i$ (1-indexed)의 실제 크기:
- 가로: $M - 2(i-1)$
- 세로: $N - 2(i-1)$
레이어가 완전한 사각형을 이루는 조건: $M - 2(i-1) \geq 2 \text{ and } N - 2(i-1) \geq 2$
즉, $i \leq \frac{\min(M,N)}{2}$일 때 완전한 레이어입니다.
Step 3: 완전 레이어의 꺾임 횟수
완전한 레이어에서는 사각형을 한 바퀴 돌면서 정확히 2번 꺾입니다:
$\text{완전 레이어 수} = \left\lfloor \frac{\min(M,N)}{2} \right\rfloor$
$\text{완전 레이어들의 총 꺾임} = 2 \times \left\lfloor \frac{\min(M,N)}{2} \right\rfloor$
Step 4: 불완전 레이어(마지막 레이어) 처리
$\min(M,N)$이 홀수인 경우, 중앙에 불완전한 레이어가 남습니다.
불완전 레이어의 형태:
- $M > N$이고 $N$이 홀수: 세로 한 줄 → 1회 꺾임
- $M < N$이고 $M$이 홀수: 가로 한 줄 → 0회 꺾임
- $M = N$이고 홀수: 중심점 하나 → 0회 꺾임
Step 5: 통합 공식 도출
케이스 분석을 통한 일반 공식:
$\text{총 꺾임 횟수} = \begin{cases} 2\left\lfloor \frac{\min(M,N)}{2} \right\rfloor & \text{if } \min(M,N) \text{이 짝수} \ 2\left\lfloor \frac{\min(M,N)}{2} \right\rfloor + \delta & \text{if } \min(M,N) \text{이 홀수} \end{cases}$
여기서 $\delta$는 불완전 레이어의 꺾임 횟수:
$\delta = \begin{cases} 1 & \text{if } M > N \text{ and } N \text{ is odd} \ 0 & \text{otherwise} \end{cases}$
Step 6: 공식 단순화
$\min(M,N) = k$라 하면:
$\left\lfloor \frac{k}{2} \right\rfloor = \begin{cases} \frac{k}{2} & \text{if } k \text{ is even} \ \frac{k-1}{2} & \text{if } k \text{ is odd} \end{cases}$
이를 이용하여 통합하면:
$T = 2\left\lfloor \frac{k}{2} \right\rfloor + \begin{cases} 0 & \text{if } k \text{ is even} \ 1 & \text{if } k \text{ is odd and } M > N \ 0 & \text{if } k \text{ is odd and } M \leq N \end{cases}$
Step 7: 최종 간소화
위 식을 다시 정리하면:
$T = k - 1 + \left\lfloor \frac{k}{2} \right\rfloor + \begin{cases} 1 & \text{if } k \text{ is odd and } M > N \ 0 & \text{otherwise} \end{cases}$
더 간단한 형태로:
$T = 2k - 1 - \mathbf{1}_{{M \leq N}}$
여기서 $\mathbf{1}_{{M \leq N}}$는 지시함수입니다.
증명:
- $M > N$인 경우: $T = 2k - 1$
- $M \leq N$인 경우: $T = 2k - 1 - 1 = 2k - 2$
1.4 공식 검증 표
| M | N | k=min(M,N) | M>N? | 예상 공식 | 실제 꺾임 |
| 3 | 4 | 3 | ✗ | 2×3-1-1=4 | 4 ✓ |
| 4 | 3 | 3 | ✓ | 2×3-1-0=5 | 5 ✓ |
| 5 | 5 | 5 | ✗ | 2×5-1-1=8 | 8 ✓ |
| 6 | 2 | 2 | ✓ | 2×2-1-0=3 | 3 ✓ |
| 1 | 7 | 1 | ✗ | 2×1-1-1=0 | 0 ✓ |
2. 알고리즘 구현 세부사항
2.1 시뮬레이션 접근법 상세 분석
def snail_simulation(M, N):
# 1. 초기 설정
matrix = [[0] * M for _ in range(N)] # N×M 행렬 (행×열)
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 동, 남, 서, 북
x, y = 0, 0 # 현재 위치 (열, 행)
direction_idx = 0 # 현재 방향 인덱스
turns = 0
# 2. 경로 추적 루프
for step in range(M * N - 1): # 마지막 칸 제외하고 이동
# 2.1 현재 위치 방문 표시
matrix[y][x] = 1
# 2.2 다음 위치 계산
dx, dy = directions[direction_idx]
next_x, next_y = x + dx, y + dy
# 2.3 꺾임 조건 검사
need_turn = False
# 경계 검사
if not (0 <= next_x < M and 0 <= next_y < N):
need_turn = True
# 이미 방문한 칸 검사
elif matrix[next_y][next_x] == 1:
need_turn = True
# 2.4 꺾임 처리
if need_turn:
turns += 1
direction_idx = (direction_idx + 1) % 4 # 시계방향 회전
dx, dy = directions[direction_idx]
next_x, next_y = x + dx, y + dy
# 2.5 위치 업데이트
x, y = next_x, next_y
return turns
2.2 핵심 로직 설명
방향 벡터 설계:
- (0, 1): 동쪽(오른쪽) - x 증가
- (1, 0): 남쪽(아래) - y 증가
- (0, -1): 서쪽(왼쪽) - x 감소
- (-1, 0): 북쪽(위) - y 감소
꺾임 감지 조건:
- 경계 이탈: 다음 위치가 표 범위를 벗어남
- 중복 방문: 다음 위치가 이미 방문된 칸
시계방향 회전:
direction_idx = (direction_idx + 1) % 4
0→1→2→3→0 순환으로 동→남→서→북 방향 전환
3. 시간/공간 복잡도 분석
3.1 공식 기반 접근법
def snail_formula(M, N):
return (min(M, N) << 1) - 1 - (M <= N)
시간 복잡도: O(1)
- 단순 산술 연산만 수행
- 입력 크기와 무관한 상수 시간
공간 복잡도: O(1)
- 추가 메모리 사용 없음
- 변수 몇 개만 사용
3.2 시뮬레이션 접근법
def snail_simulation(M, N):
matrix = [[0] * M for _ in range(N)] # O(M×N) 공간
# ... 시뮬레이션 로직
시간 복잡도: O(M×N)
- 표의 모든 칸을 한 번씩 방문
- 각 칸에서 상수 시간 연산
공간 복잡도: O(M×N)
- M×N 크기의 2차원 배열 필요
- 방문 여부 추적용
4. 시각적 예시
4.0 표를 이용한 레이어별 꺾임 분석
4×3 표의 레이어별 분해:
Layer 1 (외곽 레이어):
┌───→───→───→┐
│ 1 2 3 │4 ← 꺾임 1: 오른쪽 끝에서 아래로
│ ↓
│11 12 │5
│ ↑ ↓
│10 9 8 │6 ← 꺾임 2: 아래쪽 끝에서 왼쪽으로
└───←───←───←┘7
↑ ← 꺾임 3: 왼쪽 끝에서 위로 (내부 진입)
Layer 2 (내부 레이어):
┌─→─┐
│11 │12 ← 꺾임 4: 내부에서 오른쪽 끝 도달, 종료
└───┘
총 꺾임: 4회 (Layer 1: 2회 + Layer 2: 2회)
5×5 표의 완전한 레이어 구조:
Layer 1: 외곽 5×5 사각형
1→ 2→ 3→ 4→ 5
16 6 ← 꺾임 1
15 7
14 8
13←12←11←10← 9 ← 꺾임 2
Layer 2: 내부 3×3 사각형
17→18→19
24 20 ← 꺾임 3
23←22←21 ← 꺾임 4
Layer 3: 중심 1×1
25 (꺾임 없음)
총 꺾임: 8회 (Layer 1: 2회 + Layer 2: 2회 + 나머지 4회)
레이어 크기 변화 패턴:
| 레이어 | 원본 크기 | 레이어 크기 | 타입 | 꺾임 |
| 1 | 5×5 | 5×5 | 완전 사각형 | 2회 |
| 2 | 5×5 | 3×3 | 완전 사각형 | 2회 |
| 3 | 5×5 | 1×1 | 점 | 0회 |
$\text{레이어 } i \text{의 크기: } (M-2(i-1)) \times (N-2(i-1))$
4.1 작은 크기 표 (3×4)
최종 경로 결과:
[ 1][10][ 9]
[ 2][11][ 8]
[ 3][12][ 7]
[ 4][ 5][ 6]
꺾임 지점 분석:
- 4→5: 1회 꺾임 (오른쪽 끝에서 아래로)
- 6→7: 2회 꺾임 (아래쪽 끝에서 왼쪽으로)
- 9→10: 3회 꺾임 (왼쪽 끝에서 위로, 다음 레이어 진입)
- 10→11: 4회 꺾임 (내부 레이어에서 오른쪽으로)
총 꺾임 횟수: 4회
공식 검증: M=3, N=4, min(M,N)=3
T = 2×3 - 1 - (3≤4 ? 1 : 0) = 6 - 1 - 1 = 4회 ✓
4.2 중간 크기 표 (5×5)
최종 경로 결과:
[ 1][16][15][14][13]
[ 2][17][24][23][12]
[ 3][18][25][22][11]
[ 4][19][20][21][10]
[ 5][ 6][ 7][ 8][ 9]
꺾임 지점 분석:
- 5→6: 1회 꺾임 (오른쪽 끝에서 아래로)
- 9→10: 2회 꺾임 (아래쪽 끝에서 왼쪽으로)
- 13→14: 3회 꺾임 (왼쪽 끝에서 위로)
- 16→17: 4회 꺾임 (위쪽 끝에서 내부 레이어 진입, 오른쪽으로)
- 19→20: 5회 꺾임 (내부 레이어 오른쪽 끝에서 아래로)
- 21→22: 6회 꺾임 (내부 레이어 아래쪽 끝에서 왼쪽으로)
- 23→24: 7회 꺾임 (내부 레이어 왼쪽 끝에서 위로)
- 24→25: 8회 꺾임 (최내부 중심으로 진입)
총 꺾임: 8회
공식 검증: M=N=5, min(M,N)=5
T = 2×5 - 1 - (5≤5 ? 1 : 0) = 10 - 1 - 1 = 8회 ✓
4.4 케이스별 마지막 레이어 분석
케이스 1: M > N (세로가 더 긴 경우) - 6×3 표
실제 경로 결과:
[ 1][14][13][12][11][10]
[ 2][15][16][17][18][ 9]
[ 3][ 4][ 5][ 6][ 7][ 8]
꺾임 분석:
- 3→4: 1회 꺾임 (1,3)에서 동쪽→남쪽
- 8→9: 2회 꺾임 (6,3)에서 남쪽→서쪽
- 10→11: 3회 꺾임 (6,1)에서 서쪽→북쪽
- 14→15: 4회 꺾임 (2,1)에서 북쪽→동쪽 (내부 진입)
- 15→16: 5회 꺾임 (2,2)에서 동쪽→남쪽
총 꺾임: 5회
공식: k=3, M>N이므로 T = 2×3-1-0 = 5회 ✓
케이스 2: M < N (가로가 더 긴 경우) - 3×6 표
실제 경로 결과:
[ 1][14][13]
[ 2][15][12]
[ 3][16][11]
[ 4][17][10]
[ 5][18][ 9]
[ 6][ 7][ 8]
꺾임 분석:
- 6→7: 1회 꺾임 (1,6)에서 동쪽→남쪽
- 8→9: 2회 꺾임 (3,6)에서 남쪽→서쪽
- 13→14: 3회 꺾임 (3,1)에서 서쪽→북쪽
- 14→15: 4회 꺾임 (2,1)에서 북쪽→동쪽 (내부 진입)
총 꺾임: 4회
공식: k=3, M<N이므로 T = 2×3-1-1 = 4회 ✓
케이스 3: M = N (정사각형) - 4×4 표
실제 경로 결과:
[ 1][12][11][10]
[ 2][13][16][ 9]
[ 3][14][15][ 8]
[ 4][ 5][ 6][ 7]
꺾임 분석:
- 4→5: 1회 꺾임 (1,4)에서 동쪽→남쪽
- 7→8: 2회 꺾임 (4,4)에서 남쪽→서쪽
- 10→11: 3회 꺾임 (4,1)에서 서쪽→북쪽
- 12→13: 4회 꺾임 (2,1)에서 북쪽→동쪽 (내부 진입)
- 14→15: 5회 꺾임 (2,3)에서 동쪽→남쪽
- 15→16: 6회 꺾임 (3,3)에서 남쪽→서쪽
총 꺾임: 6회
공식: k=4, M=N이므로 T = 2×4-1-1 = 6회 ✓
4.5 레이어별 꺾임 패턴 정리
일반적인 패턴:
- 외곽 레이어: 항상 정확히 2번 꺾임 (오른쪽 끝→아래, 아래 끝→왼쪽)
- 중간 레이어들: 각각 2번씩 꺾임
- 마지막 레이어:
- M > N: 추가 꺾임 발생
- M ≤ N: 추가 꺾임 없음
수학적 검증: $T = 2 \times (\text{완전 레이어 수}) + (\text{마지막 레이어 보정})$ $= 2 \times \min(M,N) - 1 - \mathbf{1}_{{M \leq N}}$
5. 다른 해결 방법
5.1 재귀적 접근법
def snail_recursive(M, N, layer=0):
"""재귀적으로 각 레이어의 꺾임 횟수 계산"""
# 기저 조건: 더 이상 레이어가 없음
if layer * 2 >= min(M, N):
return 0
# 현재 레이어의 실제 크기
current_M = M - 2 * layer
current_N = N - 2 * layer
# 마지막 레이어 판단
if current_M == 1 or current_N == 1:
# 한 줄 또는 한 열만 남음 - 꺾임 없음
if current_M == 1 and current_N == 1:
return 0 # 점 하나
elif current_M == 1:
return 0 # 가로 한 줄
else:
return 1 # 세로 한 줄 - 마지막에 한 번 꺾임
# 일반 레이어 - 2번 꺾임 + 다음 레이어
return 2 + snail_recursive(M, N, layer + 1)
def snail_turns_recursive(M, N):
return snail_recursive(M, N)
5.2 수학적 패턴 분석 접근법
def snail_pattern_analysis(M, N):
"""패턴 분석을 통한 직접 계산"""
if M == 1 and N == 1:
return 0
if M == 1: # 가로 한 줄
return 0
if N == 1: # 세로 한 줄
return 0
# 완전한 레이어 수
complete_layers = min(M, N) // 2
# 중앙 남은 부분
remaining_M = M - 2 * complete_layers
remaining_N = N - 2 * complete_layers
# 완전한 레이어들의 꺾임: 각 레이어당 2번
turns = complete_layers * 2
# 중앙 남은 부분 처리
if remaining_M > 0 and remaining_N > 0:
if remaining_M == 1 and remaining_N == 1:
# 중앙 점 하나 - 추가 꺾임 없음
turns -= 1 # 마지막 레이어 진입 시 꺾임 제거
elif remaining_M == 1:
# 가로 한 줄 남음 - 꺾임 없음
turns -= 1
elif remaining_N == 1:
# 세로 한 줄 남음 - 1번 꺾임
turns -= 1 # 마지막 진입 꺾임만 남김
else:
# 2×2 이상 남음 - 재귀적으로 처리
pass
return max(0, turns)
5.3 동적 프로그래밍 접근법
def snail_dp(M, N):
"""메모이제이션을 사용한 동적 프로그래밍"""
memo = {}
def dp(m, n, visited_layers=0):
if (m, n, visited_layers) in memo:
return memo[(m, n, visited_layers)]
# 기저 조건
if m <= 0 or n <= 0:
result = 0
elif m == 1 and n == 1:
result = 0
elif m == 1: # 가로 한 줄
result = 0
elif n == 1: # 세로 한 줄
result = 1 if visited_layers > 0 else 0
else:
# 외곽 레이어 처리 후 내부로 이동
inner_m = m - 2
inner_n = n - 2
if inner_m > 0 and inner_n > 0:
result = 2 + dp(inner_m, inner_n, visited_layers + 1)
else:
result = 1 # 마지막 꺾임
memo[(m, n, visited_layers)] = result
return result
return dp(M, N)
5.4 기하학적 접근법
def snail_geometric(M, N):
"""기하학적 관점에서의 분석"""
# 달팽이 경로를 동심원으로 해석
# 각 원(레이어)은 직사각형 형태
total_turns = 0
current_M, current_N = M, N
while current_M > 0 and current_N > 0:
if current_M == 1 and current_N == 1:
# 중심점 도달 - 더 이상 꺾임 없음
break
elif current_M == 1:
# 가로 한 줄 - 꺾임 없이 직진
break
elif current_N == 1:
# 세로 한 줄 - 마지막에 한 번만 꺾임
total_turns += 1
break
else:
# 완전한 사각형 레이어 - 2번 꺾임
total_turns += 2
current_M -= 2
current_N -= 2
return total_turns
6. 방법별 특징 비교
| 방법 | 시간복잡도 | 공간복잡도 | 가독성 | 적용범위 |
| 수학 공식 | O(1) | O(1) | 낮음 | 모든 경우 |
| 시뮬레이션 | O(MN) | O(MN) | 높음 | 모든 경우 |
| 재귀 | O(min(M,N)) | O(min(M,N)) | 중간 | 모든 경우 |
| DP | O(min(M,N)) | O(min(M,N)) | 중간 | 복잡한 변형 |
| 기하학적 | O(min(M,N)) | O(1) | 높음 | 기본 문제 |
'Tech > Coding' 카테고리의 다른 글
| 백준 34125번: 래환이의 아이브 콘서트 이야기/맨해튼 거리 (0) | 2025.08.13 |
|---|---|
| 백준 3665번: 최종 순위 - 위상 정렬로 순위 결정하기 (0) | 2025.08.05 |
| 최장 공통 부분수열(LCS) 과 DP 역추적 (0) | 2025.07.21 |
| 파이썬 조건 매핑 함수 구현 방법 (0) | 2025.07.03 |
| 도깨비말(Pig Latin) (0) | 2025.06.23 |
