[Java] 백준 3036번 : 링 <Silver 4>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

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

3036번: 링

Code

---

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    Scanner scanner = new Scanner(System.in);

    void run(){
        int n = scanner.nextInt();
        ArrayList<Integer> ringList = new ArrayList<>();

        for(int i = 0; i < n; i++){
            ringList.add(scanner.nextInt());
        }

        for(int i = 1; i < n; i++){
            find(ringList.get(0), ringList.get(i));
        }
    }

    void find(int firstRing, int others){
        int firstTemp = firstRing;
        int othersTemp = others;
        int temp;
        while(true){
            if(firstTemp % othersTemp == 0){
                System.out.println(firstRing/othersTemp + "/" + others/othersTemp);
                break;
            }
            temp = firstTemp % othersTemp;
            firstTemp = othersTemp;
            othersTemp = temp;
        }

    }

    public static void main(String[] args) {
        Main my = new Main();
        my.run();
    }
}

---

Code 필수 요소

1. 최대 공약수 구하는 방법

2. 알고리즘의 코드구현

 

이것만 생각해내면 절반은 끝났다.

 

// 최대 공약수 구하는 방법

최대 공약수를 구하는 방법으로 가장 유명한 알고리즘이 유클리드 호제법이다.

두 숫자를 A,B라고 부르겠다. A/B를 하고 나누어떨어진다면 B가 최대 공배수이다. 하지만, 나누어떨어지지 않는다면 A%B를 시행한다. 그 후 B를 나머지 연산으로 나온 값을 이용해서 위의 방법을 반복한다.

자세한 내용은 아래 링크 참조하면 된다.

https://ko.wikipedia.org/wiki/유클리드_호제법

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

// 알고리즘의 코드 구현

유클리드 호제법을 코드로 구현하면 된다. A / B를 시도하고 나누어떨어질 경우 B가 최대공약수이다. 만약 실패할 경우 A % B를 하고, A에 B를 대입, B에 나머지 연산한 값을 대입한다. 그 후 위 내용 반복하면 된다.

이를 코드로 나타내면 find 매서드의 while문이 된다.

 

// 전체적 설명

수 입력받고 유클리드 호제법 돌려버린다. 끝

 

뭐라 할 말도 없는 문제. 유클리드 호제법을 아냐 모르냐를 물어보는 수준의 문제였다. 이게 왜 난이도 설정이 이렇게 됐는지도 모르겠다. 아 내가 이걸 알고있었어서 그런가? 뭐 쨌든 상당히 쉬웠다.

 

 

-꿑-