흰색기린

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

제목과 동일

Think🤔

최소공배수 문제했었음
최대공약수 gcd를 구한 후 
두 수의곱을 한다음 최대공약수로 나누면 그게 최소 공배수였음

gcd 최대공약수 구하는 방법

public static int gcd(int a, int b){
    if(a == 0){return b;}
    return gcd(a/b , a);
}

Solution✍

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		for(int i=0; i<n; i++){
			String input = br.readLine();
			StringTokenizer st = new StringTokenizer(input," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int gcdNum = gcd(a,b);
			System.out.println((a * b) / gcdNum);
		}
	}
	
	public static int gcd(int a,int b){
		if(b == 0){return a;}
		return gcd(b,a%b);
	}
}
% = 나머지

Review🤩

최소공배수 , 최대공약수는 외워야 함.

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

제목과 동일

Think🤔

입 : 5 2 
출 : 10

이항계수가 무엇인지 부터..

쉽게 조합을 계산할때 사용됨
10명중 3명을 뽑는 조합

분자는 10팩토리얼 
분모는 3팩토리얼 * (10-3)팩토리얼

public static Integer fac(int n){
if(n==1){return 1;}

n = fac(n-1) * n
return n;
}

Solution✍

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine(); // 한 줄로 String 받은 후
		StringTokenizer st = new StringTokenizer(input," ");
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int answer = fac(n) / (fac(k) * fac(n-k));
		
		System.out.print(answer);
	}
	
	public static int fac(int n){
		if(n==0){return 1;}
		
		int sum=1;
		for(int i=1; i<=n; i++){
			sum *= i; 
		}
		return sum;
	}
}

Review🤩

이항계수가 무엇인지 알게 됨

로또의 확률을 구할때 45개중 6개를 맞는 확률.

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

제목과 동일

Think🤔

테케 1
입 : 72
출 : 
2
2
2
3
3

입 : 9991
출 : 
97
103

int n
int i = 2;
int og = 
// 값이 1이되면 더이상 소인수 분해 못함
// i값으로 나눴을떄 나머지가 발생하면 다음 i++값으로 나눠봄
// 13이라하면
// 1,13이 나와야하니깐 같은 값이면 1출력한다음 13출력
while(n == 0){ 
	while(n % i != 0){
		if(n / i == 0){
			n = n / i;
			if(og == n){
				System.out.println(1);
				System.out.println(og);
			}else{
				System.out.println(i);
			}
		}	
	}
	i++;
}

Solution✍

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            while (n % i == 0) { // 나머지가 0이 아닐때까지
				n /= i;
				System.out.println(i);
            }
        }
    }
}

Review🤩

for문과 while문의 적절한 필요성을 느낌.

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

문제는 제목과 동일

a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 함

a : 3
b : 2

2층의 1호부터 2호까지 사람들을 데려와 살아야 함

TestCase의 수 맨처음 주어짐 2
k : 1
n : 3

k : 2
n : 3

0층부터 있음
0층의 i호에는 i명이 산다.

Think🤔

0층부터 있음
0층의 i호에는 i명이 산다.

[ 1번 케이스 ] 
1층 3호에 살고 싶으면
0층의 1호에는 1명 , 2호에 2명 , 3호에 3명 
그럼 6명을 데려와야 함.

[ 2번 케이스 ]
2층의 3호에 살고 싶으면
0층에 1,2,3 6명
1층에 1,2,3 6명
2층 1,2

그럼
0층 1호 : 1명
0층 2호 : 2명
0층 3호 : 3명

1층 1호 : 1명
1층 2호 : 0층 1호 + 0층 2호 = 1 + 2 = 3명
1층 3호 : 1+2+3 = 6명

2층 1호 : 1명 
2층 2호 : 4명 
2층 3호 : 1+3+6 = 10명

3층 1호 : 1명
3층 2호 : 5명
3층 3호 : 1+4+10 = 15명
★
0층
1 2 3 4
1층
1 3 6 10
2층
1 4 10 20
3층
1 5 15 35

n층 k호 : (n-1) 1 ~ (n-1) k
재귀 이용해서 푼다음 줄이기

public static Integer chk(int n , int k){

if(n == 0){return k;} // 각각 층이면 각 호수만큼 사람이 산다.

int re = 0;
for(int i=1; i<=k; i++){ // 전층의 k호수만큼 돌려야함
re += chk(n-1,i)
}
return re;
}

Solution✍

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main{
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer li = Integer.parseInt(br.readLine());
		
		for(int i=0; i<li; i++){
            Integer n = Integer.parseInt(br.readLine());
		    Integer k = Integer.parseInt(br.readLine());
			System.out.println(chk(n,k));
		}
	}
	
	public static Integer chk(int n , int k){

		if(n == 0){return k;}  // 0층일 경우 해당 호수만큼 사람 출력
		
		int re = 0;
		for(int i=1; i<=k; i++){ // 1명씩 있으므로 i는 1부터
			re += chk(n-1,i);
		}
		return re;
	}
}

Review🤩

재귀함수를 잘 사용해야함.

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

※ 문제는 제목과 동일합니다.

Think🤔

공식이 있으므로 바로 대입합니다.

1개의 초콜릿이 2 x 2 배열이 되려면 어떻게 되어야 하는지..

Solution✍

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str," ");
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		System.out.print(a * b - 1);
    }
}

Review🤩

문제말이 어려워서 이해하는데 오래걸림.

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

[백준] 브1 > 최대공약수와 최소공배수 2609번 - JAVA

Think🤔

자주 나오는 최대공약수와 최소공배수 문제

볼때마다 헷갈려서 이번에 정리로 다시 상기시키기.

얼핏 기억나는건 최대공약수 gcd 함수로 return 시키고 a,b값을 이용해서 재귀함수를 통해 반환.

gcd함수로 구한 최대공약수를 이용해서 최소공배수를 구했던것으로 기억.

	public static Integer gcd(int a, int b){
		int big = a;
		int small = b;
		
		if(a == b){
			return a;
		} else if(b > a){
			big = b;
			small = a;
		} 
		return gcd(big%small , small);
	}

처음엔 작은값을 구해서 뒤로 보냈는데 이렇게 하면 small이 0이되는 값을 처리하지 못하고 by zero exception을 떨어트림.

	public static Integer gcd(int a, int b){
		if(b == 0){ 
			return a;
		} 
		return gcd(b , a%b); // 작은 값 뒤로
	}

gcd(int a[큰 값] , int b[작은 값]) 되게 받아서

작은값이 0이면 더 이상 재귀를 불가능하기 때문에 앞에 있는 값이 최대공약수가 된다.

4 2 이런식으로 있으면 일단 큰 값에서 나눈 나머지 값을 가지게 되니깐 한번 진행해서 최대 공약수는 2가 된다.

그럼 최소공배수는?

		System.out.println(gcdVal);
		System.out.println((a*b) / gcdVal);

원래 있던 a = 4 , b = 2라 하면 두 수를 곱한뒤에 최대공약수로 나누면 8 / 2 = 4

최소 공배수는 4가 되게 됨.

원래 최소공배수는 원래 약수를 이용해서 계속 나눈다음 서로 크기에 곱을 해줬는데 알고리즘으로 최소공배수를 다른 식으로 풀 수 있는데 그것이 두 수를 곱한 후 , 최대공약수로 나누는 것

Solution✍

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
		int a = Integer.parseInt(str[0]);
		int b = Integer.parseInt(str[1]);
		int gcdVal = gcd(a,b); // 공배수 값
		System.out.println(gcdVal);
		System.out.println((a*b) / gcdVal);
    }
	
	public static Integer gcd(int a, int b){
		if(b == 0){ 
			return a;
		} 
		return gcd(b , a%b); // 작은 값 뒤로
	}
 }

Review🤩

편하게 외우자!