[백준] 6064 - 카잉 달력 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10이고이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력
출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

접근방법

 문제에서 요구하는 <x:y>가 몇 번째 숫자이며, 올 수없는 숫자라면 -1을 반환하는 문제이다. 해당 문제를 풀기 위해서는 최소 공배수와 각 x, y 사이의 관계식에 대해 이해해야 한다. 풀이로 들어가 보자.

풀이

 해당 문제가 왜 풀기 까다로울까 생각을 해봤다. 쉬운 문제로 예를 들어보겠다. (펼쳐서 가볍게 보는 것을 권장한다. :D)

 

중등 수학 문제였던 것 같다. 운동장 하나를 A는 10분 동안 돌고, B는 12분 동안 돈다. 이 둘이 다시 도착점에서 만나려면, 최소 몇 분이 걸릴까? 답은 두 수의 최소 공배수인 60이다. 

 

A가 한 바퀴 돌 동안 B는 2분이 늦어진다. 해당 2분이 쌓이고 쌓여서 한바퀴 차이가 날 때가 딱 60분이다. 해당 문제가 쉽게 풀리는 이유는 간단하다. 숫자가 순환하지 않고 늘어나기 때문이다. 첫 번째 바퀴를 돌 때 1분은 1분이고, 두 번째 바퀴를 돌 때 1분은 11분이다. 그렇기 때문에 특정 구간에서 A가 있을 때, B가 어디 있는지 찾기가 쉽기 때문이다.

 

이번 문제에서는 숫자를 순환하지 않는다는 차이점만 있을 뿐, 논리는 똑같다.

 

N = 10 , M= 12 인 카잉 달력에서 맨 마지막인 <10:12>를 가려면 60번이 필요하다. 그러나 문자가 순환하기 때문에, x가 1 일 때, 1이 올 수도 있고, 11 혹은 다른 숫자가 올 수도 있다는 사실을 인지해야 한다.

 

즉, 값이 순환되는 특징이 있기 때문에, 특정 X에 대해 정의역이 여러 개 나올 수 있다. 예를 들어, N =3 M =5인 경우에서 <3:2>의 값을 구한다고 가정해보자. 표를 만들면 다음과 같이 나타낼 수 있다.

 x를 기준으로, 3과 함께 올 수 있는 y의 경우는 3,1,4,2,5 이렇게 5가지의 경우다. 이를 x의 관점에서만 표현해보면 다음과 같이 표현할 수 있다. 

 

 자세히 본다면, x가 가질 수 있는 y값의 집합은 어떠한 순서를 가지고 있다. 바로 2만큼의 차이를 두고 있다. 

 

• 3 : 처음엔 3과 같은 로테이션을 취하므로,
• 1 : 처음 3보다 2칸 뒤쳐지므로,
• 4 : 1보다 2칸 뒤쳐지므로, 순환 구조를 생각했을 때 1-2+5 = 4
• 2 : 4보다 2칸 뒤쳐지므로,
• 5 : 2보다 2칸 뒤져지므로, 순환 구조를 생각했을 때 2-2+5 =2

 이처럼 2칸씩 뒤로 밀리게 된다. 그러나 0이라는 숫자가 없으므로, 값이 0 이하로 떨어질 경우 y도 마찬가지로 순환시켜주기 위해 보상값으로 5를 더한다.

 

그럼 왜 2씩 밀릴까?

3과 5의 차이가 2이기 때문이다. 3이 완벽한 순환을 이뤘을 때, 5는 2칸이 부족하게 된다. 

 

그럼 y의 집합 개수가 5개인 것도 이유가 있나?

그렇다. 둘 사이의 최소 공배수는 15이다. 3이 15가 되기 위해서는 5번의 순환을 거친다. 즉, 5번의 다른 y값을 갖게 된다는 의미이다. 

 

횟수에도 규칙성이 있다.

y의 세 번째와 y의 네 번째 값의 차이는 3이 난다. 3이 순환할 때마다 값이 바뀌기 때문이다.

 

정리하면 다음과 같다.

 

• x에 대응하는 y 값의 집합의수는  x, y의 최소 공배수에서 x를 나눈 값과 같다.
• 각 y는 |x-y|값의 차이를 가지고 순환한다.
• 한번 순환할 때마다, 횟수는 N번씩 뛴다.

이 두 개만 알고 있다면, 문제를 푸는 방법은 간단하다.

 

1. x가 가질 수 있는 y집합의 수 K를 구한다.
2. y의 기본값(둘 다 처음 시작할 때의 값)으로 부터 |x-y|씩 떨어진 K개를 구한다.
3. K 개 중 몇 번째 y 값인지 확인하고, 그만큼 N을 곱한다.
4. 해당 값이 y집합에 없다면 -1을 반환한다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stk;
        int tc = Integer.parseInt(br.readLine());
        for (int i = 0 ; i < tc ; i++){
            stk = new StringTokenizer(br.readLine()," ");
            int N = Integer.parseInt(stk.nextToken());
            int M = Integer.parseInt(stk.nextToken());
            int x = Integer.parseInt(stk.nextToken());
            int y = Integer.parseInt(stk.nextToken());

            int result ;

            if ( N<M){
                result = solution(N,M,x,y);
            }else{
                result=solution(M,N,y,x);
            }
            sb.append(result+"\n");
        }


        System.out.println(sb);

    }

    private int solution(int n, int m, int x, int y) {
        //rotation 단위
        int unit = m-n;

        //최소 공배수까지 반복 숫자
        int time_limit =0;

        //unit ==0 이라면 n 과 m 이 같다는 의미
        if(unit==0){
            //n과 m 같다면, x와y는 같은 값 밖에 안나옴
            if(x==y){
                return y;
            }else{
                //말이안됨
                return -1;
            }
        }else if ( n%unit!=0){
            //서로소 인 경우엔 x값에 대해 y값의 정의역 수가 m 개임
            time_limit =m;
        }else{
            //1이 아닌 최대공약수가 존재함을 의미 따라서 y값의 정의역은 n/unit개
            time_limit = n/ unit;
        }

        //default 자릿수(비순환시)
        int result=x;

        for (int i = 0 ; i <= time_limit+1;i++){

            if(x == y){
                result +=i*n;
                return result;
            }
            //unit만큼 빼주면서 문자 실행
            x =rotate(m,x,unit);
        }



        return -1;
    }

    private int rotate(int standard,int target, int unit){

            if(target - unit<=0){
                target-=unit;
                target+=standard;
            }else{
                target-=unit;
            }


        return target;
    }

}

결과

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.