뮤츠의 프로그래밍 이야기

이 문제를 통해 유클리드 호제법을 배웠다. 유클리드 호제법이란, a>b인 두 수 a와 b의 최대공약수는 a를 b로 나눈 나머지인 r과 b의 최대공약수이기도 한다는 것이다. 증명은 다음을 참고. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 ko.wikipedia.org 그렇다면 최소공배수는? 최대공약수를 g라 할 때, A=ag..

생각보다 쉬운 문제다. 간단히 생각하면 된다. 정수는 약수와 약수의 곱으로 되어있다. 약수를 오름차순으로 정렬한 경우를 생각해보자. 가령 12의 약수를 오름차순으로 정렬하면 1, 2, 3, 4, 6, 12이다. 눈치챘을지도 모르지만, 가장 작은 약수와, 가장 큰 약수를 순서대로 곱하면 자기자신이 나오게된다. 1 * 12 = 12, 2 * 6 = 12. 1과 자기자신이 빠졌으니, 앞뒤로 하나씩 빠진 셈이다. 받은 약수값을 정렬해서, 맨 앞 값과 맨 뒷 값을 곱해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.ut..

배수와 약수 입문문제다. a를 b로 나눈 나머지가 0, 즉 나누어 떨어질 때, b를 a의 약수, a를 b의 배수라 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while (true) { String str = br.readLine(); if (st..

아니...그사이에 단계별 풀이에서 정리해고당한 문제다. 이러면 유입이 줄어든다고! 문제는 간단하다. 중간 직사각형과, 양쪽 반원 사이에 있는지를 따지면 된다. 직사각형은 기준점인 x,y에서 대각선으로 맨끝점인 x+w, y+h 사이에 선수의 각 x, y 좌표가 있으면 된다. 원은 원의 중심에서 선수까지의 거리 d가 반지름 h/2보다 작으면 내부에 있다고 볼 수 있다. 그렇게 구해주면 끝. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { Buf..

처음에 뭔가 복잡해보여서 쫄았는데, 생각보다 간단하다. 어린왕자의 출발점에서 도착점까지 점과 점 사이로 연결되는데, 행성(원)의 진입과 이탈을 최소화한다 = 반드시 통과할때 지나가야 하는 것만 지나야 한다. 라는것이다. 그럴러면 원이 출발점과 도착점 사이에 있으면 된다. 즉, 출발점이 원의 외부에 있고, 도착점이 원의 내부에 있거나, 그 반대 (출발점이 원의 내부, 도착점이 원의 내부)에 있어야 한다는 것이다. 원의 외부인지 내부인지는, 원의 중심으로부터 점까지의 거리 d와 반지름 r을 비교하면 된다. dr이면 외부이다. d=r이면 원 위에 있는 셈인데, 문제에서 친절하게 행성의 경계에 있는 경우는 입력값에 없다고 알려주고 있다. import java.io.BufferedReader; import jav..

굳이 거리 r로 주어진 것에 주목해야한다. 한 점에서 같은 거리에 있는 점들의 집합 = 원이다. 따라서 이 문제는 두 원의 중심이 주어지고, 각각의 반지름 r1, r2가 주어졌을때 교점의 수를 구하는 문제이다. 중간에 생각대로 풀다가 틀렸길래, 구글링으로 두 원의 교점의 갯수를 찾아 풀었다. 나는 여길 참조했다. https://mathbang.net/101 두 원의 위치관계, 내접, 외접 위치관계 또 나오네요. 이번에는 두 원의 위치관계에요. 위치관계 마지막이니까 정신 바짝 차리고 따라오세요. 원과 직선의 위치관계, 원의 할선과 접선, 접점에서 했던 것처럼 두 원이 어떤 관 mathbang.net 나는 동심원의 경우를 제대로 고려하지 않았다. 배열의 크기는 6으로 고정되있어서, 반복문은 별 제한없이 써도..

면적을 구하는건 별거아닌데, 패턴 때문에 '어떻게하면 컴퓨터가 알아먹게 설명할 수 있을까?' 가 고민되는 문제. 일단 중요한 힌트는, 무조건 반시계방향으로 간다는 것. 어떤 점에서 출발하더라도, 방향이 고정되어있기에 방향을 전부 모아보면 모양을 유추할 수 있다. 예제 입력1은 ㄱ자 모양에서 우측 하단인 5시방향부터 출발하는데, 423131 순이다. 그렇다면 그 위의 점에서 출발한다면? 231314이다. 시작점만 달라지고 순서만 바뀌었다. 즉, ㄱ자모양은 1 2개, 2 1개, 3 2개, 4 1개가 나오는 꼴이다. 다른 모양도 같은 식으로 카운팅이 가능하다. 따라서 map 자료구조를 통해 1~4까지 몇번 출현했는지 카운트해서 모양을 확정짓는다. 그 후 넓이를 어떻게 구할까 생각해봤다. 처음에는 각각의 좌표를..

이걸 풀면서, 유클리드 호제법에 대해서 배웠다. A와 B의 최대공약수는, A를 B로 나눈 나머지와, B의 최대공약수와 같다, 라는것. 최소공배수는, 두 수를 곱해서 최대공약수로 나눠주면 된다. 두 수를 A, B라하고, 최대공약수를 d라 하면, A=ad, B=bd (a와 b는 서로소) A*B = ad * bd = ab * d^2 이므로, a*b*d가 최소공배수가 되고, 이 값은 AB/d가 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(Strin..

아직도 유클리드 호제법을 배우기 전이라, 그냥 브루트-포스로 무식하게 풀었다. 최대공약수는 약수 중 제일 커야하기에 위에서 아래로, 최소공배수는 배수 중 가장 작아야하기에 아래에서 위로. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str =..

자연수는 약수와 약수의 곱으로 결정된다. 따라서, 제일 작은 약수와 제일 큰 약수가 곱해지면 자기자신이 나온다. 정렬해서 맨 앞 수와 맨 끝 수를 곱해주면 끝. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStrea..