<div id="readability-page-1" class="page"><div><h2 id="문제">문제</h2>
<a href="https://www.acmicpc.net/problem/1145">적어도 대부분의 배수</a>
<img src="https://velog.velcdn.com/images/dongha1992/post/9ba07180-32b0-47df-bb76-4a0e188e6581/image.png">
<h2 id="풀이">풀이</h2>
<ul>
<li>주어진 5개의 자연수 중 적어도 3개로 나누어 떨어지는 가장 작은 수를 구해야함</li>
<li>즉, 3개 조합의 최소공배수의 최소값</li>
<li>for문 3번 중첩해서 순회하면서 모든 경우 구하고 각각 최소공배수도 구해줌</li>
</ul>
<h2 id="코드">코드</h2>
<pre><code>import java.util.Scanner;

public class Main {
 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 int[] nums = new int[5];
 
 for (int i = 0; i &lt; 5; i++) {
 nums[i] = scanner.nextInt();
 }
 
 int answer = Integer.MAX_VALUE;
 
 for (int i = 0; i &lt; 5; i++) {
 for (int j = i + 1; j &lt; 5; j++) {
 for (int k = j + 1; k &lt; 5; k++) {
 int lcm = lcm(nums[i], lcm(nums[j], nums[k]));
 answer = Math.min(answer, lcm);
 }
 }
 }
 
 System.out.println(answer);
 }
 
 // 최대공약수 
 private static int gcd(int a, int b) {
 if (b == 0) {
 return a;
 }
 return gcd(b, a % b);
 }
 
 // 최소공배수
 private static int lcm(int a, int b) {
 return a * (b / gcd(a, b));
 }
}</code></pre>
<h2 id="정리">정리</h2>
<ul>
<li>최소공배수, 최대공약수 구하는 거 까먹어서 인터넷 봄...</li>
</ul></div></div>

삶도 재입학이 되나요?

문제
적어도 대부분의 배수
풀이
주어진 5개의 자연수 중 적어도 3개로 나누어 떨어지는 가장 작은 수를 구해야함
즉, 3개 조합의 최소공배수의 최소값
for문 3번 중첩해서 순회하면서 모든 경우 구하고 각각 최소공배수도 구해줌
코드
import java.util.Scanner;
public class Main {
 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 int[] nums = new int[5];
 for (int i = 0; i < 5; i++) {
 nums[i] = scanner.nextInt();
 }
 int answer = Integer.MAX_VALUE;
 for (int i = 0; i < 5; i++) {
 for (int j = i + 1; j < 5; j++) {
 for (int k = j + 1; k < 5; k++) {
 int lcm = lcm(nums[i], lcm(nums[j], nums[k]));
 answer = Math.min(answer, lcm);
 }
 }
 }
 System.out.println(answer);
 }
 // 최대공약수 
 private static int gcd(int a, int b) {
 if (b == 0) {
 return a;
 }
 return gcd(b, a % b);
 }
 // 최소공배수
 private static int lcm(int a, int b) {
 return a * (b / gcd(a, b));
 }
}
정리
최소공배수, 최대공약수 구하는 거 까먹어서 인터넷 봄...

99클럽 코테 스터디 35일차 - 완전탐색

댓글