곽로그

[백준 6064, Java] 카잉달력 본문

알고리즘/백준

[백준 6064, Java] 카잉달력

일도이동 2020. 11. 30. 23:33
반응형

문제

www.acmicpc.net/problem/6064

 

6064번: 카잉 달력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다.

www.acmicpc.net

첫번째 풀이(시간초과)

 

 가장 간단한 풀이다. year, yearX, yearY를 하나씩 증가시키면서 yearX, yearY가 각각 x 와 y랑 같은지 체크해준다. 이때 yearX, yearY를 증가시킬 때 M, N을 넘으면 1로 초기화 시켜준다. (근데 다시 풀이를 보니까 종료조건도 틀려있다) 

 그런데 이 풀이의 시간복잡도는 O(MN)이다. 카잉달력의 마지막 날은 <M,N>인데 이를 1씩 카운트 하면 MN의 최소 공배수까지 가게된다. M,N의 최대 값이 40,000 인데 M*N = 1,600,000,000 은 1억을 넘어가므로 시간초과가 난다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int T;
    public static int destX;
    public static int destY;
    public static int x;
    public static int y;
    public static int N;
    public static int M;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine().trim());
        for(int t = 0; t<T ; t++){
            st = new StringTokenizer(br.readLine()," ");
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            destX = Integer.parseInt(st.nextToken());
            destY = Integer.parseInt(st.nextToken());

            int result = calculateYear();
            bw.write(String.valueOf(result)+"\n");
        }
        bw.flush();

        br.close();
        bw.close();

    }
    public static int calculateYear(){
        int x = 0;
        int y = 0;
        int count = 0;
        boolean valid = true;
        while (true) {
            x = x<M ? ++x : 1;
            y= y< N ? ++y : 1;
            ++count;

            if(x==destX && y == destY){
                valid = true;
                break;
            }

            if(x==M && y == N){
                valid = false;
                break;
            }
        }

        return valid ? count : -1;
    }
}

 

두번째 풀이(틀림)

 서로 자리올림 단위가 다를 때는 모듈러 연산을 생각할 수 있다. 10진수를 해당 진수로 나눈 나머지 (예를 들어 10을 M으로 나눈 나머지, 10을 N으로 나눈 나머지)로 주기를 이루기 때문이다. 

 

M = 10 이고 N = 12인 경우 x는 10이 주기고, y는 12가 주기다.  만약 <3: 9>를 구한다고 하면 3은 <3:9>까지 10진수로 count한 수를 10(M)으로 나눈 나머지가 3이고, 9는 count를 N으로 나눈 나머지가 9이다. 이 성질을 이용해서 x를 구한다음 이때의 count를 N으로 나눈 나머지가 y인지를 확인하면 된다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int T;
    public static int M;
    public static int N;
    public static int x;
    public static int y;
    public static void main(String[] args) throws Exception{
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        for(int t= 0 ;t<T; t++) {
            st = new StringTokenizer(br.readLine(), " ");
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            int deadYear = getDeadYear();
            int result = getYear(deadYear);

            bw.write(String.valueOf(result)+"\n");
        }

        bw.flush();

    }
    public static int getDeadYear(){
        //M과 N의 최소 공배수
        int m = M;
        int n = N;
        while(n>0){
            int r = m % n;
            m = n;
            n = r;
        }

        //최소공배수 = M * N / 최대공약수(m)
        return M * N / m;
    }
    public static int getYear(int deadYear){
        boolean isValid = true;
        int year = x;
        while(true){
            if(year>deadYear){
                isValid = false;
                break;
            }
            if(year % N ==y){
                isValid = true;
                break;
            }
            year +=M;
        }
        return  isValid ? year : -1;
    }
}

 

 

세번째 풀이

 두번째 풀이에서 생각하지 못했던 것은 year % N == y부분인데, 만약 N == y 이면 year % N ==0 인경우를 체크하지 못한다

따라서 이 부분에 대한 처리를 따로 해줘야한다. (반례 10 12 10 12)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int T;
    public static int M;
    public static int N;
    public static int x;
    public static int y;
    public static void main(String[] args) throws Exception{
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        for(int t= 0 ;t<T; t++) {
            st = new StringTokenizer(br.readLine(), " ");
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            int deadYear = getDeadYear();
            int result = getYear(deadYear);

            bw.write(String.valueOf(result)+"\n");
        }

        bw.flush();

    }
    public static int getDeadYear(){
        //M과 N의 최소 공배수
        int m = M;
        int n = N;
        while(n>0){
            int r = m % n;
            m = n;
            n = r;
        }

        //최소공배수 = M * N / 최대공약수(m)
        return M * N / m;
    }
    public static int getYear(int deadYear){
        boolean isValid = true;
        int year = x;
        while(true){
            if(year>deadYear){
                isValid = false;
                break;
            }

            int tempYear = year % N ==0? N : year %N;
            if(tempYear == y){
                isValid = true;
                break;
            }
            year +=M;
        }
        return  isValid ? year : -1;
    }
}

 

함수 안쓰는 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int t, m, n, x, y;

        t = Integer.parseInt(br.readLine());
        for(int testCase = 0; testCase<t; testCase++){
            st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            x  = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());


            int xx = x;
            int year = xx;
            int yy = year%n==0? n : year%n;

            while(true){
                //현재 x,y가 목표 x, y인가
                if(xx == x && yy == y){
                    break;
                }
                //현재 x, y가 카잉달력의 마지막 해인가(-> year의 마지막)
                else if(year>m*n){
                    year = -1;
                    break;
                }
                //현재 x,y가 목표해도 아니고 마지막 해도 아니면 다음 해를 구한다
                else{
                    year +=m;
                    xx = year%m==0? m : year%m;
                    yy = year%n ==0? n: year%n;
                }
            }
            bw.write(String.valueOf(year)+"\n");
        }
        bw.flush();
    }
}

 

시간복잡도는 O(N) - xx를 고정시킨 후 yy를 검사하는데, yy에서 나올 수 있는 경우의 수는 N개

반응형
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

[백준 1912, Java] 연속합  (0) 2020.12.07
[백준 1748, Java] 수 이어 쓰기1  (0) 2020.12.01
[백준 2579, Java] 계단 오르기  (0) 2020.11.27
[백준 1905, Java] 01타일  (0) 2020.11.27
[백준 3085, Java] 사탕 게임  (0) 2020.11.27
'알고리즘/백준' Related Articles more
Comments