목록수학 (75)
기록방
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/DyfEw/btsFGjekpeY/ABFO4OJtln1W8MlrJ5B2LK/img.png)
👉 문제링크 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 🔸 문제 분석 🔸 주사위 M개에 대해 i번째 주사위의 면 개수는 Ni, 면의 모든 값의 총합은 Si로 입력된다. 모든 주사위를 던졌을 때의 기대값을 계산한다. S1/N1 + S2/N2 + ... + SM/NM 계산의 어려움 때문에 임의의 분수 a / b를 모듈러를 이용해 (a * b-1 mod x)의 정수 값으로 계산한다. 🔸 문제 풀이 🔸 문제의 수학 이론 설명이 꽤 길지만, 읽어보면 이해 못할 정도는 아니다. 보다 정확한 확률 계산을 위해 모듈러 표현 방식을 사용한다는 것이다. 문제에서 제시된 공식을..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bbQWem/btsFjLcl6V6/9EKa1Fp96SmTuTalPw5ptk/img.png)
👉 문제링크 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 🔸 문제 분석 🔸 10 이하의 자연수 N이 주어지고, N-1 개의 재료 비율이 주어진다. 칵테일을 만드는데 필요한 각 재료의 최소 질량을 출력한다. 🔸 문제 풀이 🔸 기준값을 찾기 위해 입력된 p, q 비율들의 최소공배수를 구한다. N개의 재료와 N-1의 연결 정보는 N개의 노드와 N-1의 간선 정보이므로 트리 형태로 나타낼 수 있다. 한 노드에 값을 넣고 DFS로 인접한 노드를 탐색하며 입력된 비율로 각 노드의 질량 값을 만들어 간다. 모든 노드의..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/erbT6V/btsE96GeD3F/wbtKWwJVqOPU3Y9DeiHh11/img.png)
👉 문제링크 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 🔸 문제 분석 🔸 A와 B의 길이만큼 1로 이루어진 수의 최대공약수를 구하는 문제이다. 🔸 문제 풀이 🔸 실제 수는 아주 긴 1로 이루어진 숫자들이지만, 그냥 A와 B의 최대공약수를 구하면 되는 문제이다. 유클리드호제법을 사용해서 최대공약수를 구하고, 그 수만큼 반복해서 1로 이루어진 수를 만들어 출력한다. 🔸 코드 🔸 import java.io.*; import java.util.StringTokenizer; public cl..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/r247Y/btsE6JrRzhN/kiolQ9t43S7cFjFx5eFFPK/img.png)
👉 문제링크 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔸 문제 분석 🔸 1부터 자연수 n까지의 범위에서, 최대공약수(GCD)가 1인 자연수의 개수를 구하는 문제이다. 다시 말하면 서로소의 개수를 구하는 문제이다. 🔸 문제 풀이 🔸 서로소 개수를 구하는 공식으로 오일러의 피 함수(Euler product formula; 오일러 곱 공식)을 사용한다. n의 소인수로 P[i] = P[i] - P[i]/K (i는 K의 배수) 연산을 반복한다. n이 소수이거나, n이 지수가 1인 소인수를 가지는 경우, 오일러 피 함수를 1회 더 적용한다. 🔸 코드 🔸 impo..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/btQFbV/btsE1Ce0HMS/NXYlkeAzbLne8zhwM9AVUk/img.png)
👉 문제링크 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 🔸 문제 분석 🔸 주어진 범위에서 1보다 큰 수의 제곱수로 나누어 떨어지지 않는 수의 개수를 출력한다. 최소값이 1부터 1조, 최대값은 최소값부터 100만을 더한 값까지 주어진다. 🔸 문제 풀이 🔸 min과 max의 값이 1조까지 크게 주어지므로 long으로 받야아 한다. 제곱수를 확인하기 위해 에라토스테네스의 체 알고리즘을 사용한다. 배열의 크기를 max-min+1 만큼 차이로 선언한다. 제곱수의 배수를 max까지 계산하며 에라토스..