페르마의 소정리 사용 문제. https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 페르마의 소정리에 대해서는 백준님이 깔끔하게 정리해 주셨습니다. https://www.acmicpc.net/blog/view/29 페르마의 소정리를 통해 역원을 구해주면, 역원의 곱을 통해 나눗셈을 대체할 수 있으며, 따라서 mod연산을 할때 나눗셈을 하지않고 구할수 있게 됨. 쿼리가 10만개를 넘기 때문에, O(logN)시간에 제곱연산을 수행해주는 함수 pow를 직접 작성..
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 정올같은데에서 본거같은 문제이다. #include #include #include #include char arr[11][10]; int table[128] = {0}; // 문자 - 숫자 대응 배열. int main(){ int n,tmp,sum=9,ans=0; scanf("%d", &n); for(int i=0; i
무난하게 풀었다. https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 쇠막대기를 레이저로 자를때, 앞에서 센 '(' 의 개수 = 쇠막대기의 수 만큼 기존 막대기가 분리가 되며, ')'를 통해 쇠막대기가 끝남을 알릴때도 잘린곳 - 쇠막대기의 끝 으로 이어지는 쇠막대기가 하나 더 생기기 때문에 이부분만 잘 처리해주면 AC가 나온다. #include #include char input[123456] = {0}; int main(){ int ans=0; int su..
실버작 겸 감을 잃지않기위해 무난한난이도 문제를 풀고있다. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 방문여부를 검사하는 visit배열을 만들어서 탐색후 visit배열에 남은 방문한곳들을 더하고 마지막으로 처음 시작한 1을 빼주면 AC. #include #include using namespace std; vector arr[101]; int visit[101] = {0}; void search(int node){ for(int i=0; i
의외로 고민했는데 원인이 되게 의미없는거엿다 테스트케이스가 하나밖에 없어서 좀 고민한 문제이다. https://www.acmicpc.net/problem/1059 1059번: 수2 첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다 www.acmicpc.net 일단 첫번째 코너케이스 1 3 1 과 같은 경우에는 0을 가상의 left값으로 잡고 문제를 해결하면 된다. 두번째 1 998 999 과 같은 경우에는 1001을 가상의 right값으로 잡고 문제를 해결하면 된다 세번째 4 1 3 5 7 3 N이 Lucky Set 안에 있는 경우 답은 항상 ..
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net Ai는 Ai-1의 배수라는 조건덕분에 그리디알고리즘으로 해결 가능한 문제이다. Ai-1번째 k개를 선택해서 값을 채우느니 그냥 k배인 Ai를 사용하면 동전 수를 절약할 수 있기때문에 (100원 다섯개 vs 500원 한개의 차이) 가장 큰 동전부터 계산해서 지불해야하는 금액을 줄여나가면 된다. #include int main(){ ..