과제 36

[donasman]

과제 진행 공통 방식

1. 매주 일요일까지 주어진 문제를 푼다.
2. 매주 일요일 저녁 진행자가 차주 과제를 공지.
3. 알고리즘 난이도에 따라 문제수는 매주 달라질 수 있다.
4. 적절한 소통을 위해 상대방이 푼 문제에 코멘트를 달아준다.
5. 주어진 문제를 푸는 언어는 상관이 없다.

---

과제 36

기간: 12월 28일(일)
과제: 백준 알고리즘 15단계 약수, 배수와 소수 2

• 1735 분수합
• 2485 가로수

[donasman]

문제: 1735 분수합
언어: Java 11

import java.util.Scanner;
	
public class Main {

    public static void main(String[] args) throws Exception {
    	
        Scanner sc = new Scanner(System.in);
        	
    	int a = sc.nextInt(); // a/b
    	int b = sc.nextInt();
    	
    	int c = sc.nextInt(); // c/d
    	int d = sc.nextInt();
    	
    	int denominator = b*d;
    	int molecule = (a*d) + (c*b);
    	int gcd = gcd(molecule, denominator);
    	
    	System.out.println(molecule / gcd + " " + denominator/gcd);
        
    }
    
    public static int gcd(int a, int b) { //최대공약수
    	while(b != 0) {
    		int r = a % b;
    		a = b;
    		b = r;
    	}
    	return a;
		
	}
    
    public static int lcd(int a, int b) { // 최소공배수
    	int gcd = gcd(a, b);
		return (a * b) / gcd;
	}
}

이 문제에서는 최소공배수는 안썼지만 편의상 앞 서 만들어둔 함수를 그대로 적어봤습니다.

기약분수로 만들기 위해선 서로 나눠지지 않는 수가 되어야 하기에 최대공약수를 나눠 기약분수로 만들어줬습니다.

[donasman]

문제: 2485 가로
언어: Java 11

import java.util.Scanner;
	
public class Main {

    public static void main(String[] args) throws Exception {
    	
        Scanner sc = new Scanner(System.in);
        	
    	int n = sc.nextInt();
    	int[] arr = new int[n];
    	for(int i = 0; i < n; i++) {
    		arr[i] = sc.nextInt();    		
    	}
    	int gcd = 0;
    	for(int i = 0; i < n-1; i++) {
    		int dist = arr[i + 1] - arr[i];
    		gcd = gcd(dist, gcd);
    	}
        System.out.println((arr[n-1] - arr[0])/gcd+1-(arr.length));
    }
    
    public static int gcd(int a, int b) { //최대공약수
    	while(b != 0) {
    		int r = a % b;
    		a = b;
    		b = r;
    	}
    	return a;
		
	}
    
    public static int lcd(int a, int b) { // 최소공배수
    	int gcd = gcd(a, b);
		return (a * b) / gcd;
	}
}

먼저 나무의 위치를 배열에 넣은 후 나무 사이의 간격을 구해, 간격들에 최대공약수를 구하면 가장 크고 일정한 간격을 가질 수 있게 됩니다. 필요한 총 나무개수를 먼저 구해 이미 있는 나무 개수를 빼면 더 심어야 될 나무 개수를 구할 수 있습니다. 필요한 총 나무 갯수는 (마지막 나무 위치 - 첫 번째 나무 위치) / 최대공약수 계산 하면 전체 간격의 개수가 나옵니다. 여기에 + 1 을 하면 나무의 개수로 사용 할 수 있습니다. 다른 식으로는 (전체거리 / 최대공약수) + 1 을 한다고 생각을 해도 좋을 것 같습니다. 전체 나무 개수에서 있는 나무 개수를 빼 필요한 나무 개수를 구해주면 문제를 해결 할 수 있습니다.

[dev-xong]

건희씨 엄청 간결하고 심플하게 가로수 문제를 푸셨네요.
제거 풀고 건희씨거 보는데 배울점이 많네요
클린코드를 보는 것 같습니다 (실제로 그럼)

36주차도 고생하셨습니당.
제가 너무 늦게 풀었네요!! 분발하겠습니다!