[백준알고리즘] 브루트포스 - 6064번 카잉 달력 문제

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

6064번: 카잉 달력

1.

전에 했던 년도 계산 문제와 비슷하게 풀릴까 하고 거의 똑같이 코드를 짜서 했지만 백준 사이트에서 시간초과가 떴다.

그럼 그렇지..이 문제를 강의에서 다루는데에는 이유가 있겠지..

반복을 마지막 해인 <M:N>이 되기 전까지만 하도록 했는데

표현 불가능한 수를 끝까지 다 돌려보려니 시간이 초과가 되나 싶어서

어떻게 해야 표현 가능할지 아닐지를 돌려보기 전에 판단할수 있을까 이리저리 고민해보았지만 모르겠다.

강의를 살짝 봤는데 다른 방법으로 푸는 듯 하다(아무래도..)

찾고자 하는 날짜까지 더 빠르게 접근하도록 풀이해야 하는 듯 하다

얼핏 봤는데 아직 이해가 안 가서, 내일 다시 보고 이해해보고 코드를 짜 보도록 하겠다

 

사이트에서 시간초과 뜬 코드

package baekjoonWeek3;

import java.io.*;
import java.util.StringTokenizer;

public class KyingCalendar {    //백준 6064번 카잉달력 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());    //입력받을 테스트케이스 수
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());   //x년도의 범위:1~M
            int N = Integer.parseInt(st.nextToken());   //y년도의 범위:1~N
            int X = Integer.parseInt(st.nextToken());   //x년도
            int Y = Integer.parseInt(st.nextToken());   //y년도

            int count = 0;
            int x = 0; int y = 0;
            while (X != x || Y != y) {
                if (x == M && y == N) { //마지막 해가 될떄까지도 답이 안나오면 표현불가, -1출력
                    count = -1;
                    break;
                }
                if (x == M) {
                    x = 1;
                } else {
                    x++;
                }
                if (y == N) {
                    y = 1;
                } else {
                    y++;
                }
                count++;
            }
            bw.write(Integer.toString(count));
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}

 

2.

이 밑에있는 코드는 건너 뛰면서 하는 방법에 대한 힌트를 얻고 수정해 짠 코드이다

그러나 마찬가지로 시간초과가 떴다(말고도 답도 제대로 안나왔을듯)

이전에 푼 날짜계산 문제와는 다르게 이번 문제에서는 M,N의 범위가 최대 40000이기 때문에

가능한 M,N의 조합이 최대 16억개 되어버린다는걸 알아야 한다

1억이 대략 1초이므로 최악의 경우 16초가 나오게 되는것

강의에서 사용한 반복문이 끝나는 조건은 for문으로 M*N을 넘지 않되, 증가값을 M으로 해서 M씩 건너뛰는 식이다.

나는 최악의 경우(-1이 출력되어야 할 경우) y가 돌아가다가 언젠가는 x와 같아지는 시점이 되었을때까지 보게 했는데,

그 같아지는 시점이 모호해서 쓸데없이 많이 반복되게 한 듯 하다.

그리고 또 잘못된 부분들이 있는데, 일단 y의 초기값으로 X를 할당하면 안된다. (N의 범위가 M보다 작을경우)

하더라도 %N해서 나머지값을 초기값으로 하던지 해야한다.

그리고 나머지값이 0으로 나올경우를 생각을 안했다. 예를들어 N == Y라면 이 경우를 고려할수가 없다

뭐 여기저기 문제 많았던 코드였다..

package baekjoonWeek3;

import java.io.*;
import java.util.StringTokenizer;

public class KyingCalendar {    //백준 6064번 카잉달력 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());    //입력받을 테스트케이스 수
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());   //x년도의 범위:1~M
            int N = Integer.parseInt(st.nextToken());   //y년도의 범위:1~N
            int X = Integer.parseInt(st.nextToken());   //x년도
            int Y = Integer.parseInt(st.nextToken());   //y년도

            int count = X;  //X로 일단 시작
            int x = X; int y = X;   
            while (Y != y) {   
                if (x == y && count > X) { //마지막 해가 될떄까지도 답이 안나오면 표현불가, -1출력
                    count = -1;
                    break;
                }
                y = (y + M) % N; //x기준 한바퀴 돌렸을때 Y의값 갱신
                count += M;
            }
            bw.write(Integer.toString(count));
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}

 

3.

뜯어고쳐서 제출하고 드뎌 맞았습니다가 떴다.

원래는 for문 조건을 강의대로 for (int j=X; j<N*M; j+=M) { 로 했었는데,

결국 반복을 N번만큼만 하면 되는구나 하는 깨달음을 얻고 딱 N번만 반복문을 수행하도록 해 보았다

나머지가 0이 나올 경우도 고려하여 애초에 다 -1씩 빼고 마지막에 count계산할때 +1했다

마찬가지로 맞았습니다가 뜬다

package baekjoonWeek3;

import java.io.*;
import java.util.StringTokenizer;

public class KyingCalendar {    //백준 6064번 카잉달력 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());    //입력받을 테스트케이스 수
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());   //x년도의 범위:1~M
            int N = Integer.parseInt(st.nextToken());   //y년도의 범위:1~N
            int X = Integer.parseInt(st.nextToken());   //x년도
            int Y = Integer.parseInt(st.nextToken());   //y년도

            int count = -1;  //반복 다해봤는데 답없으면 -1출력
            X -= 1; Y -= 1;   //둘다 1씩 뺴서 생각한다.왜냐면..나머지를 이용해야하는데 N이 5고 Y가 5인 경우 나머지가 0이나오기때문
            int k = X;
            for (int j=0; j<N; j++) {   //N번 확인한다
                if (k % N == Y) {   //나머지값이 Y가되면 정답
                    count = k + 1;  //애초에 -1해서 생각했으니 다시 1을 더한값이 원래 값이 된다
                    break;
                }
                k += M;
            }
            bw.write(Integer.toString(count)); 
            bw.newLine();


        }
        bw.flush();
        bw.close();
    }
}

 

수학에 약해서 그런지..풀면서 이런저런 의문들이 많았어서 풀어보는데 생각보다 오래걸렸던 문제이다

필요없는 부분들은 건너뛰면서 최악의 경우 마지막 경우의 수까지 살펴보는 방법..습득~~