boj)6064 - 카잉 달력
2020. 9. 22. 16:33ㆍPS/boj
import java.io.*;
import java.util.StringTokenizer;
public class boj_6064 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
public static void main(String[] args) throws IOException {
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()) - 1;
int y = Integer.parseInt(st.nextToken()) - 1;
boolean isOk = false;
for (int j = x; j < m*n; j+=m) {
if (j % n == y) {
System.out.println(j+1);
isOk = true;
break;
}
}
if (!isOk) System.out.println(-1);
}
}
}
생각
- 날짜 계산의 문제와 유사하게 1부터 쭉 반복문을 돌려가며 찾을려고 생각했음
- 근데 m,n의 범위가 각각 4만이라서 O(N^2)의 풀이의 경우 시간초과
- 풀이가 생각이 안나면 손으로 하나씩 적어보자
풀이
- 숫자를 적어나가다 보면 나머지 규칙이 있음
- x, y 값 중 하나를 고정 시키고 그 값의 범위만큼 널뛰기 하면 나머지 하나의 값만 변하게 되고
계속 반복하다 보면 언젠간 나오게 되어있음
- 풀이에서는 초기값을 x에 고정시키고 여기서 x의 범위인 m만큼 널뛰기하면 x값은 고정이고
j % n == y를 만족할때까지 반복하면 됨
- 초기에 x, y를 -1씩 해줘야 나머지가 딱 맞게 떨어질 수 있음
- 출력시에는 처음에 뺏으니 +1 해준다
'PS > boj' 카테고리의 다른 글
boj)10773 - 제로 (0) | 2020.10.12 |
---|---|
boj)1748 - 수 이어쓰기 1 (0) | 2020.09.22 |
boj)14500 - 테트로미노 (0) | 2020.09.22 |
boj)1107 - 리모컨 (0) | 2020.09.22 |
boj)1476 - 날짜 계산 (0) | 2020.09.21 |