알고리즘 풀이/백준

[백준][Java] 6064번 카잉 달력

배게 2018. 4. 29. 20:22
728x90

너무 어려웠습니다.


반례 예시는 해당문제의 질문검색 나와있는

https://www.acmicpc.net/board/view/21503 를 참조하였고


알고리즘의 전반적인 틀은

http://andamiro25.tistory.com/93 를 참조하였습니다.


문제에서 요구하는 (x,y)가 몇 번째 해인지 찾는 가장 쉽고 무식한 방법은

N부터 1씩 증가하시키는 경우입니다. 하지만 M,N의 최대값이 40000이기 때문에

while문을 최대 40000*40000번을 돌리는 경우가 생겨

시간초과할 것이 분명하므로 패스하였습니다.


도저히 풀이법을 못찾아서 구글링하다 찾은 방법은

<x:y>의 x와 y중 작은 값 하나를 고정시키는 방법입니다.

이를 이용하면 while문은 최대 약 40000번까지만 돌리면 모든 경우의

수를 해결할 수 있습니다.


이 방법을 알고도 제가 정의를 실수한 부분은


m_n=((m_n+smaller_unit)%bigger_unit==0)?bigger_unit :(m_n+smaller_unit)%bigger_unit ;


이 부분인데 기존에는

m_n= (m_n+smaller_unit)%bigger_unit

이런식으로 정의해서

 12 6 12 6 인 경우에 x의 값이 0이 되는

경우를 간과한 것입니다.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int k = sc.nextInt();
		int [][]input = new int[k][4];
		int []res = new int[k];
		
		
		for(int i=0; i<k; i++) {
			for(int j=0; j<4; j++) {
				input[i][j] = sc.nextInt();
			}
		}
		
		for(int i=0; i<k; i++) {
			int m_n=0;
			int count =0;
			int bigger_unit,smaller_unit, final_mn;
			
			if(input[i][2]>=input[i][3]) {
				m_n=input[i][3];
				res[i]=input[i][3];
				bigger_unit = input[i][0];
				smaller_unit = input[i][1];
				
				final_mn=input[i][2];
			}
			else {
				m_n=input[i][2];
				res[i]=input[i][2];
				bigger_unit = input[i][1];
				smaller_unit = input[i][0];
				
				final_mn=input[i][3];
			}
			
			while(true) {
				if(m_n==final_mn) {
					res[i]+=count*smaller_unit ;
					break;
				}
				else if(count==bigger_unit) {
					res[i]=-1;
					break;
				}
				else {
					count++;
					m_n=((m_n+smaller_unit)%bigger_unit==0)?bigger_unit :(m_n+smaller_unit)%bigger_unit ;
				}
				
			}
			
		}
		
		for (int i : res) {
			System.out.println(i);
		}
		
	}
}


댓글수0