알고리즘95 백준[자바 java] 1446번 : 지름길 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 문제설명 D킬로미터를 가야하는 세진이가 운전해야하는 거리의 최솟값을 구하는 문제이다. 풀이설명 다이나믹 프로그래밍을 사용하여 문제를 푼다. 지름길의 갯수만큼 배열을 만들어 거기에 지름길들을 입력받는다(arr) dp배열을 D만큼 만들고 배열에 각각의 수를 넣어준다(지름길이 없을 때의 운전해야하는 거리) dp에는 각각의 거리에 도달할 때 운전해야 하는 최솟값을 넣어준다. 우선 현재 위치보다.. 2023. 7. 11. 백준 [java 자바] 2251번 : 물통 문제를 보고 처음 계획을 세울 때 감이 잘 잡히지 않았던 문제이다. import java.util.*; import java.io.*; class three { int a; int b; int c; three(int a, int b, int c){ this.a = a; this.b = b; this.c = c; } } class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); StringBuilder sb.. 2022. 8. 19. 백준 [자바 java] 7576번 : 토마토 처음 봤을 때에는 평소에 많이 봤던 문제인 것 같아서 쉽다고 생각했는데 시간 초과가 나서 조금 헷갈렸다. import java.util.*; import java.io.*; class Main{ static int n; static int m; static int[][] arr; static int k = 0; static int ok() { int ok = 1; for(int i = k;i 2022. 8. 19. 백준 [자바 java] 1495번 : 기타리스트 분명 처음 봤을 때에는 dp라고 생각했지만 막상 어떻게 풀어야 할지 생각이 나지 않아서 스택 두 개로 주고받고 하는 형식으로 풀었었다. 하지만 가차 없이 메모리 초과가 났다. 예전에 한번 풀어봤던 것 같아서 이제까지 풀었던 dp문제를 다시 쭉 봤다. 그 중 안녕이라는 문제와 제일 비슷했다. dp는 최댓값을 저장하고 나머지를 버린다라는 고정관념이 있었는데 이 dp는 한계 수가 있으면 그만큼 수열을 만들어주고 해당하는지 아닌지 표시하는 방식이다. import java.util.*; import java.io.*; class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader.. 2022. 8. 14. 백준 [java 자바] 1629번 : 곱셈 이 문제는 정말 오랜만에 혼자 해결하지 못한 문제입니다. 아무리 풀어도 답이 나오지 않아서 다른 블로그 글을 참고했고 덕분에 분할 정복에 대해 알게 되었습니다. 언뜻 보기에는 쉬워 보이지만 사실 굉장한 장애물이 있습니다. 바로! 입력받은 수를 곱하면 long자료형이어도 넘어갈 수 있다는 것이다. 그래서 내가 다른 방법으로 풀었을 때 방법은 맞지만 틀렸습니다가 나온 이유인 것 같다. 이 문제에서 가장 중요한 개념은 거듭제곱을 분할하는 것 그러니까 10^5 = 10^2 * 10^2 * 10 이렇다는 것을 이용하는 것이다. 그리고 (a*a)% c와 (a% c)*(a% c)% c는 같다는 것이다. 근거는 (a*c + b)*(a*c+b) 하고 c로 나누어주면 어차피 남는 것은 b*b이기 때문이다. package .. 2022. 8. 13. 백준 [java 자바] 2447번 : 별찍기-10 이 문제는 예전에도 도전해 본 적이 있는데 그때는 이걸 어떻게 푸나 하고 넘어갔지만 지금은 풀 수 있어서 기분이 좋았다. 확실히 꾸준히 하니 실력이 느는 것 같다. 이제까지는 실버 1문 제 만 풀었는데 이제 골드 5로 넘어가고자 한다. 빨리 골드로 승급하고 싶다! n은 3의 x제곱이고 x만큼 저 패턴을 반복한다고 보면 된다. import java.util.*; import java.io.*; class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBu.. 2022. 8. 12. 이전 1 ··· 11 12 13 14 15 16 다음
