본문 바로가기

전체 글312

[JAVA] 백준 11402 - 이항 계수 4 https://www.acmicpc.net/problem/11402이항 계수 (N,K)를 M으로 나눈 나머지를 구하는 문제이다.일반적으로 N!*(K!*(N-K)!)^M-2를 구해 문제를 푸는데 N의 범위가 10^18이다.페르마의 소정리와 DP 팩토리얼만 이용했다간 팩토리얼 구하는 부분에서 문제가 터질 것이다.따라서 루카의 정리를 이용해 문제를 풀었다. 루카의 정리란, 이항 계수 (N,K)를 M으로 나눈 나머지를 구할 때, N과 K를 M진법으로 나타낸 수의 각 자릿수(N1,K1)의 이항계수를 M으로 나눈 나머지를 누적해 곱하면 (N,K)를 M으로 나눈 나머지와 같다는 정리이다. 루카 페르마 이놈들은 천재가 틀림없다.import java.io.BufferedReader;import java.io.IOExce.. 2025. 10. 10.
[JAVA] 백준 13977 - 이항 계수와 쿼리 https://www.acmicpc.net/problem/13977https://ghcode.tistory.com/304 [JAVA] 백준 11401 - 이항 계수 3https://www.acmicpc.net/problem/11401https://ghcode.tistory.com/302 [JAVA] 백준 11051 - 이항 계수2https://www.acmicpc.net/problem/11051이항 계수 (N,K)를 10,007로 나눈 나머지를 구하는 문제이다.이항 계수(N,K)란 nCk를 의미하ghcode.tistory.com이항 계수 3 문제를 M개의 testcase를 주고 해결하는 문제이다. 동일한 구현(dp 팩토리얼 + 빠른 제곱)으로 풀었더니 통과했다.인생 첫 플레티넘 문제인데 공짜로 얻은 듯한.. 2025. 10. 10.
[JAVA] 백준 1939 - 중량제한 https://www.acmicpc.net/problem/1939https://ghcode.tistory.com/286 [JAVA] 백준 1800 - 인터넷 설치https://www.acmicpc.net/problem/1800K개의 무료 연결을 제외한 나머지 (경로 - K)개의 케이블선의 가중치의 MAX값의 최솟값을 구하는 문제이다.첫번째로 일반적인 다익스트라로 JAVA의 comparable 인터페이스ghcode.tistory.com인터넷 설치 문제와 마찬가지로 이분탐색을 이용해 조건을 비교하며 범위를 줄여나가서 정답을 도출하는 문제이다.나는 처음에 이분탐색을 돌리면서 [mid값 이하의 도로로 물건을 목적지까지 옮길 수 있는지]의 조건으로mid 이 조건이 잘못 되어서 시간을 많이 잡아먹었다.목표하는 정보.. 2025. 10. 10.
[JAVA] 백준 32197 - 절연 구간 최소화 https://www.acmicpc.net/problem/32197정점 A, B를 포함한 N개의 정점이 주어질 때, 간선의 상태 (직류 ==0, 교류 ==1)이 교차되는 -> 절연이 발생하는 횟수가 최소가 되는 경로의 가중치를 구하는 문제이다. 첫 노드의 경우는 교류/직류 구분이 없으므로 count하지 않고, 그 외의 경우에는 노드가 현재 가지고 있는 상태와 간선의 상태를 비교해 절연이 발생할 경우 가중치를 +1 해줬다. 절연이 발생하지 않는 간선을 뽑을 경우의 부등호 조건을 잘못 넣어서 한참 고민했다.ㅠㅠ import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arr.. 2025. 10. 9.
[JAVA] 백준 23793 - 두 단계 최단 경로 1 https://www.acmicpc.net/problem/23793 정점 X,Y,Z를 포함한 N개의 정점이 주어질 때, X->Y->Z 경로의 최단 길이와, X->Z(Y 포함하지 않음)의 최단 길이를 구하는 문제이다.https://ghcode.tistory.com/300 [JAVA] 백준 18223 - 민준이와 마산 그리고 건우https://www.acmicpc.net/problem/18223민준이가 1에서 V까지 최단경로로 갈 때, 건우를 데려갈 수 있으면 SAVE HIM, 아닐 경우 GOOD BYE를 출력하는 문제이다. 민준이가 1에서 출발해 건우까지 가는 최단 경로와ghcode.tistory.com민준이가 마산으로 갈 때 건우를 데려갈 수 있는지 여부를 판단하는 문제와 비슷한데, 이번 문제는 Y를 포.. 2025. 10. 9.
[JAVA] 백준 22865 - 가장 먼 곳 https://www.acmicpc.net/problem/22865N개의 도시 중 3개의 정점에서 가장 먼 곳을 찾는데, 가장 먼 곳 = 3개의 정점에서 가장 가까운 곳의 최댓값이다. 3개의 정점 정보를 입력받는데, 중복이 될 수 있으므로 distinct해서 관리하고,distinct한 개수만큼 다익스트라를 돌린 뒤 각 정점간의 거리의 최솟값의 최댓값을 가진 정점의 index를 반환했다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util... 2025. 10. 9.

티스토리툴바