원형거리 계산

JunHyeok Seo·2025년 3월 3일

완전탐색 원형거리계산

algorithm

목록 보기

6/30

두 가지로 열리는 자물쇠 문제 분석 및 해결 방법

문제 개요

1부터 N까지의 숫자로 이루어진 3자리 다이얼이 있는 자물쇠가 있음
자물쇠는 원형 구조이며, 1과 N이 인접한 형태로 연결됨
두 가지의 숫자 조합이 주어졌을 때, 어느 한 조합이라도 모든 숫자가 거리 2 이내이면 자물쇠가 열림
자물쇠가 열리는 서로 다른 조합의 개수를 구하는 문제

원형 거리 계산 (Circular Distance Calculation)

자물쇠가 원형이므로 거리 계산 시 원형 구조를 고려해야 한다.
즉, 일반적인 차이 계산이 아닌 원형 거리를 적용해야 함.

원형 거리 공식

두 숫자 x와 y 사이의 원형 거리는 다음과 같이 계산됨:

distance(x, y) = \min(|x - y|, N - |x - y|)

일반 거리: |x - y|
원형을 고려한 거리: N - |x - y|
두 거리 중 작은 값을 선택하여 원형 거리를 결정함

이 원리를 이용하여 특정 숫자가 기준 숫자에서 2 이내에 있는지를 판별할 수 있다.

코드 구현

코드 설명

isWithinRange(int x, int y, int n): 주어진 숫자 x가 기준 숫자 y에서 원형 거리 2 이내인지 확인하는 함수
3중 루프를 이용해 모든 가능한 조합을 탐색하며, 주어진 두 조합 중 하나라도 조건을 만족하는 경우 개수를 증가시킴

Java 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
        int a2 = sc.nextInt(), b2 = sc.nextInt(), c2 = sc.nextInt();
        sc.close();

        int count = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    if (isWithinRange(i, a, n) && isWithinRange(j, b, n) && isWithinRange(k, c, n)
                        || isWithinRange(i, a2, n) && isWithinRange(j, b2, n) && isWithinRange(k, c2, n)) {
                        count++;
                    }
                }
            }
        }

        System.out.println(count);
    }

    private static boolean isWithinRange(int x, int y, int n) {
        int dist = Math.min(Math.abs(x - y), n - Math.abs(x - y));
        return dist <= 2;
    }
}