[백준] 단계별로 풀어보기(단계:17,정수론 및 조합론,JAVA)3036번, 링

문제 링크

3036번: 링

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 예제 입력을 통해 알고리즘을 알아보면

예제 입력1.

8 4 2

8/4 -> 2/1(최대공약수 : 4)

8/2 -> 4/1(최대공약수 : 2)

예제 입력2.

12 3 8 4

12/3 = 4/1(최대공약수 : 3)

12/8 = 3/2(최대공약수 : 4)

12/4 = 3/1(최대공약수 : 4)

규칙을 보면 첫 값에 다음 링들의 값들을 나눈 후에 약분을 취해주는데 더 이상 약분이 되지 않으려면 최대공약수로 약분을 하면 됩니다.

그래서 두 링의 수의 최대 공약수를 구한 뒤 (첫 번째링/다음 링)에서 최대 공약수로 약분을 진행해주면 됩니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 띄어쓰기 기준으로 링의 크기들을 저장하였습니다.
• 최대 공약수 구하는 함수 GCD를 만들었습니다.(유클리드 호제법)
• for문을 통하여 위에 알고리즘을 이용하여 GCD 함수를 사용하여 최대 공약수를 구하여 분모와 분자를 약분해주었스니다.
• BufferedWriter을 사용하여 결과를 출력하였습니다.

• GCD는 유클리드 호제법을 이용하여 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int index;	//링 개수
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //--------------입력 값 저장--------------
    	index = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int basic = Integer.parseInt(st.nextToken());
    	for(int i=1;i<index;i++) {
        	int temp = Integer.parseInt(st.nextToken());
        	int gcd = GCD(basic,temp);
            //결과 BufferedWriter에 저장
        	bw.write(basic/gcd + "/" + temp/gcd + "\n");
    	}
    	bw.flush();	//결과 출력
    	bw.close();
    	br.close();
	}
    //----------------최대 공약수 구하는 함수-----------
    //유클리드 호제법 사용
	public static int GCD(int num1, int num2) {
		if(num2==0)
			return num1;
		else
			return GCD(num2, num1%num2);
	}
}