[JAVA] 백준 1584 - 게임 https://www.acmicpc.net/problem/1584500*500 사이즈의 맵에서 위험구역(생명력-1), 죽음의구역(진입불가)를 거쳐 500,500에 도달했을 때 필요한 최소 생명수를 구하는 문제이다.map에 0 -> 안전, 1 -> 위험, 2-> 죽음으로 표시해놓고 다익스트라를 위한 우선순위큐를 map의 flag 기준으로 정렬해 구했다. 우선순위큐 타입은 int[]로 했는데, 처음에 i, j, map flag로 구성했다가 메모리 초과가 나서 i,j,누적 소비 생명으로 바꾸고 통과했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;imp.. 2025. 9. 23. [JAVA] 백준 5972 - 택배 배송 https://www.acmicpc.net/problem/5972일반적인 다익스트라 문제이다.두 정점을 잇는 간선의 개수가 1개 이상이라 최솟값만 저장하도록 노드 클래스에 HashMap으로 최솟값만 먼저 받고, 생성된 Key-Value 쌍을 간선list로 변환해 저장한 후 다익스트라를 돌렸다. 중복간선 처리는 다익스트라 내부에서 충분히 가능하니 굳이 HashMap을 사용하지 않아도 되고, NodeClass도 weight 배열로 가능할 것 같다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;import java.util.stream.Collectors;publ.. 2025. 9. 22. [JAVA] 백준 1446 - 지름길 https://www.acmicpc.net/problem/1446다익스트라를 풀고 싶어서 Solved.ac에서 다익스트라 태그를 붙여서 찾은 문제이다.다익스트라 태그를 타고 들어갔기 때문에 문제를 보고 바로 그리디하게 정렬할 수 있는 기준을 열심히 찾았는데아무리 봐도 그 기준이 모호했다. 하나를 고치면 다른 곳에서 구멍이 났다.그래서 N도 작겠다 그냥 DFS로 풀었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List.. 2025. 9. 21. [JAVA] 백준 11444 - 피보나치 수 6 https://www.acmicpc.net/problem/11444N번째 피보나치수를 10억 7로 나눈 나머지를 출력하는 문제이다.N의 범위를 보면 알듯 일반적으로 사용하는 동적계획법이나 재귀를 이용해 풀면 반드시 시간초과가 난다.F(n+1) = F(n)+F(n-1)라는 점화식을 이런 식으로 나타낼 수 있으므로 (1 1 1 0) 행렬의 거듭제곱으로 N번째 피보나치수를 구할 수 있다고 한다.이런 걸 어떻게 알아내는거지..여튼 이걸 알았으니 일반적인 빠른 제곱 알고리즘을 이용해 풀었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static long .. 2025. 9. 17. 이전 1 ··· 11 12 13 14 15 16 17 ··· 78 다음