알고리즘 풀이/백준43 [BOJ] 9370. 미확인 도착지 - JAVA 🔗 문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 그래프 이론, 다익스트라 풀이 문제는 시작정점에서 목적지 정점까지 가는 최단 경로 중 g-h 또는 h-g 를 포함하는 목적지를 찾는 것이다. g-h 를 뺀 나머지 간선들의 비용은 짝수로, g-h 는 홀수로 변경해서 만약, 최단경로가 홀수라면 g-h 를 포함한 경로이므로 목적지 후보에 포함시킨다. 느낀 점 이걸 어떻게 생각하지... 전체 코드 impor.. 2023. 2. 6. [BOJ] 2004. 조합 0의 개수 - JAVA 🔗 문제 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 수학, 정수론 풀이 문제는 nCr 의 0의 갯수를 구하는 것이다. 여기서 수학 공식 한 개를 알아야 한다. 우선 팩토리얼의 0의 갯수부터 구해보자. 예를 들어서 59! 의 0의 갯수를 구하려면 59! 을 소인 수 분해 했을 때 2 x 5 의 갯수가 몇 개인지 찾아야 한다. (10 이 몇 번 곱해졌는 지가 0의 갯수를 결정하므로) 59! = 59 x 58 x 57 x ... x 1 이다. 이 중 5의 배수는 59/5 .. 2023. 2. 2. [BOJ] 1676. 팩토리얼 0의 개수 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 수학, 임의 정밀도 / 큰 수 연산 풀이 일단 뒤에 0이 붙는다는 건 2 x 5 가 곱해져 있을 떄다. 즉, 소인수분해를 해서 2 x 5 쌍의 갯수만큼 뒤에 0이 붙는다는 의미이다. 예를 들어, 30은 30 = 2×3×5 로 2와 5의 쌍이 1 개 이므로 0이 1개 붙는다. 조금 더 큰 수로 예를 들면 231400 의 경우 2와 5의 쌍이 2개 이므로 0이 2개가 붙는다. (231400) 팩토리얼과 소인수분해를 쭉 나열해 보면 다음과 같다. .. 2023. 1. 27. [BOJ] 2981. 검문 - JAVA 🔗 문제 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 수학, 정수론, 유클리드호제법 헤맸던 문제다.. 풀이 방법을 보면 어떻게 저런 생각을 해내는지 신기하다. 문제에 나온 임의의 정수를 나타내면 다음과 같다. (M : 나눈수, r : 나머지) A1 = M * a1 + r1 A2 = M * a2 + r2 여기서 찾아내야 하는게 가능한 모든 M 이 되고, 나머지가 같기 때문에 r1 과 r2 가 같다. 따라서 여기서 A1 과 A2.. 2023. 1. 24. [BOJ] 3036. 링 - JAVA 🔗 문제 https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 정수론, 유클리드 호제법 유클리드 호제법 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하.. 2023. 1. 20. [BOJ] 1004. 어린왕자 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 수학, 기하학 그림에 겁먹을 것 없이 풀이과정은 은근 단순했다. 진입/이탈의 최소 횟수를 구하는 것이기 때문에 출발점과 도착점이 원 밖에 있다면, 진입/이탈 없이 돌아서 가면 된다. 출발점과 도착점이 둘 다 원 내부에 있다면 진입/이탈이 없기 때문에 횟수로 치지 않는다. 즉, 출발점 또는 도착점 중 하나가 원 내부에 있다면 무조건 진입/이탈을.. 2023. 1. 19. 이전 1 2 3 4 5 6 7 8 다음
