[백준] code.plus(브루트포스,JAVA)6064번, 카잉 달력

문제 링크

6064번: 카잉 달력

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제를 처음 접근할 때 M,N을 +1씩 하는 방식으로 진행하였지만 시간초과가 발생하였습니다.

그래서 종이에 끄적이다가 규칙을 발견하였습니다.

찾는 x와 y값에서 x값을 고정으로 y값이 나올 수 있는 값들을 찾습니다.

y값이 나온다면 그에 해당하는 연도를 출력하고 나오지 않는다면 해당 연도는 유효하지 않는 것으로 -1을 출력하도록 하면 +1로 계속 확인하는 것보다 훨씬 시간복잡도가 좋겠다고 생각하였습니다.

예제입력 1에 13 11 5 6 일 때 표현해보겠습니다.

 

x = 5로 고정하고 나올 수 있는 수를 확인해보겠습니다.

 

x = 5, y = 5

 

x = 5, y = 7

 

x = 5, y = 9

 

x = 5, y = 11

 

x = 5, y = 2

 

....

 

x = 5, y= 5

 

위에 순서대로 처음 x = 5, y = 5로 돌아오게 됩니다.

x = 5, y = 5로 돌아올 때까지 입력된 y값이 발견되지 않으면 해당하는 연도는 유효하지 않는 것으로 판단하면 됩니다.

 

여기서 x값을 고정했을 때 y값을 구하는 방법을 설명해보도록 하겠습니다.

 

x이 5에서 다시 5가 된다는 것은 M의 값만큼 +1을 진행하였을 때 5가 나옵니다.

 

y에 값에서도 M만큼의 값을 +1을 진행하고 y는 N을 기준으로 표현되기 때문에 N으로 나머지를 구해주는 것입니다.

 

공식은

 

x = 5이면 (5 + M) % M = 5

 

y = (y+M) % N

 

예제 처음 x=5, y=5일 때 위 공식을 대입하면

 

x = (5+13)%13 = 5

 

y = (5+13)%11 = 7

 

x=5, y=7이 나온다는 것을 확인할 수 있습니다.

 

마지막으로 공식에서 하나 신경써야 할 부분이 존재합니다. 만약 (y+M)%N = 0일 경우입니다.

 

(y+M)%N = 0인 경우 나머지를 구하면 0이 결과로 나오기 때문에 따로 조건을 처리해주면 됩니다.

 

저는 (y+M)%N == 0 이면 y값을 N이 되게 조건을 처리해주었습니다.

 

예제에 x = 5, y = 9일 때 다음 수를 확인하면

 

x = (5+13) % 13 = 5

 

y = (9 + 13) % 11 = 0

 

9+13 = 22 이므로 나머지가 0이 나오는데 실제 y의 값은 11입니다. 

 

이럴 때를 대비해서 나머지가 0이 나오면 y = N이 되도록 조건처리하였습니다.

 

문제에 해결알고리즘은

1. 입력된 x의 값을 고정값으로 생각합니다.

2. (y+M) % N을 진행하여 나올 수 있는 y의 값을 얻습니다.

3. 나온 y의 값이 입력값 y값과 동일하면 해당 연도를 출력합니다.

4. 위 과정을 반복하여 입력값 y의 동일한 값이 존재하지 않는다면 -1을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringToknizer을 이용하여 M, N, x, y를 저장하였습니다.
• 카잉 달력에 관한 연도를 구하는 kayingYear함수를 만들었습니다.
• BufferedWriter에 함수 실행으로 입력값에 해당 연도를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• kayingYear은 x값을 고정으로 두고 입력값 y에 해당하는 y값이 존재하는지 확인하도록 반복하였으며 존재하지 않는다면 -1을 반환하였습니다.
• kayingYear은 (y+M)%N 공식을 삼항연산자와 if문을 써서 구현하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-----입력값 저장 및 함수 실행------
    	StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++) {
        	st = new StringTokenizer(br.readLine()," ");
        	int M = Integer.parseInt(st.nextToken());
        	int N = Integer.parseInt(st.nextToken());
        	int x = Integer.parseInt(st.nextToken());
        	int y = Integer.parseInt(st.nextToken());
        	bw.write(kayingYear(M, N, x, y) + "\n");	//함수 결과 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //카잉 달력 현재 연도 구하는 함수
    public static int kayingYear(int M,int N,int x,int y) {
    	/*
        처음 x의 값을 고정하기 위해 x의 값만큼 +1을 진행해야 하므로
        기본 연도의 값을 x로 설정하였습니다.
        */
    	int result = x;
    	int tempY = x%N==0 ? N : x%N;	//삼항연산으로 처음 y의 값 구하기
    	if(tempY == y)	//x를 고정한 첫 x,y값이 입력값과 동일한 경우
    		return result;
    	int check = tempY;	//x를 고정한 첫번째 y값 저장
        //--------입력값 y가 존재하는지 확인-------
    	while(true) {
    		tempY = (tempY+M)%N;
    		if(tempY==0)
    			tempY=N;
    		result += M;
    		if(tempY == y)		//존재할 때
    			break;
    		if(tempY==check)	//존재하지 않을 때(첫번째 y값으로 돌아왔을 때)
    			return -1;
    	}
    	return result;
    }
}