BOJ 4117 - Combination Lock

문제

BOJ 4117 - Combination Lock

N개의 눈금이 있는 자물쇠 다이얼을 조작하는 최소 회전 수를 구하는 문제이다. 다이얼은 세 개가 있으며, 현재 위치 t[0], t[1], t[2]에서 목표 위치로 이동해야 한다. 자물쇠를 열기 위해 첫 번째 다이얼은 반시계 방향으로 2바퀴 이상 돌리고, 이후 두 번째와 세 번째 다이얼을 특정 방향으로 돌리는 조작에 필요한 총 클릭 수를 계산한다.

입력

• 여러 테스트 케이스가 주어지며, 0이 입력되면 종료한다.
• 각 케이스마다 N t[0] t[1] t[2]가 주어진다 (다이얼 눈금 수와 세 다이얼의 현재 위치).

출력

각 케이스마다 자물쇠를 여는 데 필요한 총 클릭 수를 출력한다.

예제

풀이

조합 자물쇠의 조작 규칙에 따라 수식 4*N - 1 + (t[1]-t[0]+N)%N + (t[1]-t[2]+N)%N을 계산하는 수학 문제이다.

1. N과 t[0], t[1], t[2]를 읽는다. N이 0이면 종료한다.
2. 자물쇠 조작 순서:
   • 첫 번째 다이얼을 반시계 방향으로 2바퀴 이상 돌려 t[0] 위치에 맞춘다: 고정 비용 4*N - 1 (2바퀴 = 2N 클릭 + 추가 이동).
   • 두 번째 다이얼을 시계 방향으로 돌려 t[1] 위치에 맞춘다: (t[1] - t[0] + N) % N 클릭.
   • 세 번째 다이얼을 반시계 방향으로 돌려 t[2] 위치에 맞춘다: (t[1] - t[2] + N) % N 클릭.
3. 세 값의 합을 출력한다.

핵심 아이디어: 조합 자물쇠의 관행적인 조작 규칙(반시계 2바퀴 → 시계 방향 → 반시계 방향)을 수식 하나로 표현한다. 모듈러 연산 (a - b + N) % N은 원형 다이얼에서 두 위치 간의 시계/반시계 방향 이동 거리를 계산한다.

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	while (1) {
		int n, t[3];
		cin >> n >> t[0] >> t[1] >> t[2];
		if (n == 0)break;
		cout << 4 * n - 1 + (t[1] - t[0] + n) % n + (t[1] - t[2] + n) % n << '\n';
	}
}

복잡도

• 시간: O(T) — 테스트 케이스 수만큼 단순 사칙연산
• 공간: O(1) — 변수만 사용하는 상수 공간