전체 글312 [JAVA] 백준 22116 - 창영이와 퇴근 https://www.acmicpc.net/problem/22116각 정점별 값 차이를 최소로 하는 경로로 이동할 때, 경로의 값의 최댓값의 최솟값을 구하는 문제이다.첫번째로 mid 값으로 답을 정해놓고 하는 이분 탐색으로 시도했다가 시간초과를 맞고우선순위큐 정렬 기준을 경로의 max값으로 지정해놓고 돌렸는데 offer 기준을 최단경로 기준으로 잡아놔서 또 틀렸다가offer 기준을 값차이의 max값으로 돌린 뒤 정답을 받았다.괜히 시간을 많이 잡아먹었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.PriorityQue.. 2025. 10. 9. [JAVA] 백준 11401 - 이항 계수 3 https://www.acmicpc.net/problem/11401https://ghcode.tistory.com/302 [JAVA] 백준 11051 - 이항 계수2https://www.acmicpc.net/problem/11051이항 계수 (N,K)를 10,007로 나눈 나머지를 구하는 문제이다.이항 계수(N,K)란 nCk를 의미하고 이는 곧 N!/K!*(N-K)!를 의미하며 이것은 N! * (K!*(N-K)!)^-1이다.따라서 문제에서ghcode.tistory.com이항계수와 모듈러 역원을 복습하기 위해 풀어본 문제이다.N의 범위와 Mod 값이 달라져서팩토리얼을 재귀방식 -> DP로 바꿨고 long type으로 선언했다.그 외에는 동일하다. N의 범위가 10^18인 문제도 있는 것을 보니 팩토리얼을 .. 2025. 10. 9. [JAVA] 백준 13379 - Far Far Away https://www.acmicpc.net/problem/13379쉬고 싶은 대학교 강사들을 위한 [대학교 -> 학술회] 최장거리를 구하는 문제이다.방향 그래프가 주어지고 DFS, BFS, 다익스트라 등 다양한 방법으로 풀 수 있는데 익숙한 다익스트라를 이용했다.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.PriorityQueue;public class Main { public static void main(String[] a.. 2025. 10. 9. [JAVA] 백준 11051 - 이항 계수2 https://www.acmicpc.net/problem/11051이항 계수 (N,K)를 10,007로 나눈 나머지를 구하는 문제이다.이항 계수(N,K)란 nCk를 의미하고 이는 곧 N!/K!*(N-K)!를 의미하며 이것은 N! * (K!*(N-K)!)^-1이다.따라서 문제에서 요구하는 것은 N! * (K!*(N-K)!)^-1 % 10007이다.문제는 이제 (K!*(N-K)!)의 p에 대한 모듈러 역원을 구해야 하는데, 모듈러 역원이란 a * x ≡ 1 mod p 로 표시하고 이는 어떤 값 x에 a를 곱했을 때 그 값을 p로 나눴을 때 나머지가 1인 수를 의미한다.예를 들어 a=3이고 p가 7일 때 3의 7에 대한 모듈러 역원은 5이다. 3 * 5 /7 == 1이기 때문이다. 페르마의 소정리는 a !≡0.. 2025. 10. 9. [JAVA] 백준 20007 - 떡 돌리기 https://www.acmicpc.net/problem/20007성현이가 출발점에서 한 정점씩 왕복할 때, 모든 정점을 왕복하는데에 몇일이 소요되는지 구하는 문제이다.먼저 다익스트라로 각 정점까지의 최단 거리를 구한 후 만약 도달하지 못하는 정점이 있으면 -1을 반환하고 종료했다.그리고 왕복거리로 설정하기 위해 각 최단 거리를 2배 해준 뒤 하루 최대 이동거리를 초과할 경우에도 -1을 반환하고 종료했다.마지막으로 최단 거리 배열을 정렬한 뒤 최대 이동거리를 몇번 채울 수 있는지 구한 후 반환했다. 다익스트라를 함수로 빼서 사용해봤는데 훨씬 편하다.자주 이용해야겠다. import java.io.BufferedReader;import java.io.IOException;import java.io.Input.. 2025. 10. 8. [JAVA] 백준 18223 - 민준이와 마산 그리고 건우 https://www.acmicpc.net/problem/18223민준이가 1에서 V까지 최단경로로 갈 때, 건우를 데려갈 수 있으면 SAVE HIM, 아닐 경우 GOOD BYE를 출력하는 문제이다. 민준이가 1에서 출발해 건우까지 가는 최단 경로와 마산까지 가는 최단 경로의 가중치를 첫번째 다익스트라로 구하고,건우 위치에서 마산으로 가는 최단 경로의 가중치를 두번째 다익스트라로 구한 뒤,(1 -> 건우) + (건우 -> 마산) 마산) 일 경우는 SAVE, 아닐 경우 굿바이를 출력했다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;impo.. 2025. 10. 8. 이전 1 2 3 4 5 6 7 ··· 52 다음