백준 문제 18512번 점프 점프

문제 출처:

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

18512번: 점프 점프

점프 점프 문제

이번에 해당 문제에 대해 이런식으로 접근해 보았습니다.

//P_18512

#include <iostream>

using namespace std;

int main(){

    int X, Y, P1, P2 ;
    cin >> X >> Y >> P1 >> P2 ;
    int x1 = 0, x2 = 0 ;
    int y1, y2 ;
    if(둘이 만나지 않는 조건){
        do{
            y1 = X * x1 + P1 ;
            y2 = Y * x2 + P2 ;
            if(y1 < y2)
                x1 ++ ;
            else
                x2 ++ ;
        }while(y1 != y2);
        cout << X * x1 + P1 ;
    }
    else
        printf("-1") ;
    
    return 0 ;
}

비교적 간단한 코드로 로직에 여러 문제가 있을 수 있지만 이런 방식으로 진행을 하면 되지 않을까라는 생각이었습니다.

하지만 둘이 만나지 않을 조건을 정하는 것이 떠오르질 않았습니다.

또한 이렇게 하는 방법으로 해당 조건을 거르고 테스트를 해보았을때

주어진 시간보다 많은 시간을 사용한다는 것을 발견하였습니다.

​

그렇기 때문에 제 코드는 여러번 시간 초과를 표출하였고 저보다 대단하신 분들의 코드를 참고하고자 하였습니다.

​

이분 코드를 참고하였습니다.

https://dlwnsdud205.tistory.com/61

[백준 / BOJ] 18512 점프 점프

전체적인 로직은 비슷하다고 생각했으나 이런 방법이 더 빠르다는 것을 알게된 시간이었습니다.

//
//  main.cpp
//  18512 점프 점프
//
//  Created by 이준영 on 2020/10/05.
//

#include <iostream>

using namespace std;

int X, Y, P1, P2;
int check1[10000205];

void find_LCM(int num1, int num2){
    for(int i = 0; i <= 100000; i++){
        check1[num1 + (X*i)] = 1;
    }
    for(int i = 0; i <= 100000; i++){
        if(check1[num2 + (Y*i)] == 1){
            cout << num2 + (Y*i) << "\n";
            return;
        }
    }
    cout << -1 << "\n";
    return;
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio();
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> X >> Y >> P1 >> P2;
    find_LCM(P1,P2);
    return 0;
}

추가적으로 이 코드에서 쓰인 아래의 요소들은 처음 보았기에 어떤 것인지 찾아보았습니다.

ios::sync_with_stdio(); //defalut value는 true 
cin.tie(NULL);
cout.tie(NULL);

- C와 C++ 간의 I/O 스트림 동기화

​

cin, cout의 시간을 줄여줄 수 있는 코드라고 합니다.

https://raylee00.blog.me/222038557757

C++ 입출력 속도와 ios_base::sync_with_stdio(false), cin.tie(NULL) 에 관한 글

​

앞으로 더 열심히 공부해야겠다 생각했습니다

 

해당 부분은 아래의 Github에서도 보실 수 있습니다.

https://github.com/gurcks8989/CodingTest/blob/master/BackJoon/HPS/P18512_JumpJump.cpp

GitHub - gurcks8989/CodingTest: BackJoon_study_with_c++

 

훈수 및 조언은 언제든지 환영입니다.