전체 글242 [백준] 10282: 해킹 - JAVA https://www.acmicpc.net/problem/10282 풀이문제풀고 바로 블로그에 써야하는데 게을러서 늦게 쓰는 풀이.. a가 b를 의존하고 있다면, b가 감염되고 일정 시간 뒤 a도 감염된다. 따라서, b에서 a로 가는 경로가 있다고 생각했다. 이런 관계들을 `ArrayList`에 담아주었다. 감염된 컴퓨터 c부터 시작하여 다익스트라 알고리즘을 통해 경로를 따라갔다. 다익스트라 알고리즘은 최단 경로를 알려주는데, b에서 a로 감염될 때 걸리는 시간을 가중치로 두고 진행했다. 최종적으로 dist배열의 값이 INF가 아닌것들을 세주면 끝. 메모리: 148832KB시간: 784ms언어: Java 11import java.io.*;import java.util.*;public class Mai.. 2024. 7. 18. [백준] 19542: 전단지 돌리기 - JAVA https://www.acmicpc.net/problem/19542 풀이트리모양의 길 위에서 전단지를 돌리는데, 현재 노드에서 거리가 d이하인 노드들에는 현재 노드에서 전단지를 돌릴 수 있다. 따라서, 어떤 노드로부터 리프 노드까지의 거리가 d이하라면 더이상 앞으로 나아가지 않아도 된다는 것이다. dfs탐색을 통해 리프까지의 최대 거리를 구한다. 해당 거리가 d이상이라면 `cnt`값을 늘려줬다. 다시 시작 정점으로 돌아와야 하므로 `cnt * 2`가 정답이 된다. 메모리: 70564KB시간: 456ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int s, d, cnt; static ArrayList> g.. 2024. 7. 13. [백준] 25195: Yes or yes - JAVA https://www.acmicpc.net/problem/25195 풀이방향그래프가 주어지고, 1번 정점에서 출발해 리프노드까지 도달해야한다. 이때, 팬클럽이 위치하는 정점들을 피해 리프노드까지 도달할 수 있는지 확인하는 문제이다. dfs탐색의 인자로 팬클럽을 만났는지 여부를 담아 진행했다. 리프노드에 갔을 때 팬클럽을 만난적이 없다면 boolean값을 갱신해준다. 방문처리를 하지 않고 진행했는데 그 이유는 주어진 그래프가 사이클이 없음이 보장되었고, 방문처리를 할 경우 1 -> 2 -> 4 의 루트로 여행했다면, 1 -> 3 -> 4 의 루트로 여행하는 것은 이미 4번 정점이 방문처리 되었기 때문에 진행이 안되는 문제가 있었기 때문이다. 따라서, 방문처리 없이 바로 이전 정점으로만 갈 수 없게 했다. .. 2024. 7. 13. [백준] 21278: 호석이 두 마리 치킨 - JAVA https://www.acmicpc.net/problem/21278 풀이건물들이 도로로 연결되어있고, 2개의 건물을 골라 치킨집을 열어야 한다. 이때, 치킨집으로부터 각 건물들까지의 거리의 합이 최소가 되게 해야한다. 먼저 플로이드-워셜 알고리즘을 통해 각 건물들 사이의 거리를 구했다. for (int k = 1; k 건물들 사이의 거리를 구한 후, 2개의 건물을 정해 거리의 합을 계산해 정답을 갱신해주었다. 메모리: 17220KB시간: 192ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] dist; public static void main(String[.. 2024. 7. 13. [백준] 22114: 창영이와 점프 - JAVA https://www.acmicpc.net/problem/22114 풀이뭔가 문제를 이해하는데 오래걸렸다... 컨디션 난조?? 아무튼.. n개의 블럭들 사이에 거리가 얼마나 떨어져있는지 n-1개의 숫자가 주어진다. `(블럭) 2 (블럭) 3 (블럭) 1 (블럭) 5 (블럭) 3 (블럭) 5 (블럭)` 이렇게 블럭이 위치하고있는것이다. 이차원 dp배열을 만들었다. [n][2] 사이즈로 만들어서 [i][0]의 경우 점프를 하지 않은 경우, [i][1]의 경우 점프를 한 경우이다. 다음 블럭까지 거리가 k보다 크다면 [i][1]에 [i-1][0]값에 1을 더해주고, [i][0]에는 점프를 하지 않았을 때 해당 블럭부터 시작한다는 의미로 1을 넣어준다. k보다 작다면 이전값에서 1씩 더해준다. 값을 더하면서 정.. 2024. 7. 1. [백준] 1239: 차트 - JAVA https://www.acmicpc.net/problem/1239 풀이원형 차트를 만들 때, 각 구간의 비율이 주어진다. 각 구간을 적절히 배치했을 때 원의 중심을 지나는 선의 개수를 최대로 해야한다. 어떤 구간합이 50이 되면 원의 중심을 지나는 선이 생긴다. 순열을 만들어 각 구간들을 어떻게 배치할지 정했다. 이때, set을 이용해 중복제거를 해줬다. 구해진 순서를 슬라이딩윈도우 방식으로 구간합이 50이 되는 개수를 찾아 정답을 갱신해줬다. 메모리: 49480KB시간: 416ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, answer; static int[] arr, selected; .. 2024. 6. 27. [백준] 2228: 구간 나누기 - JAVA https://www.acmicpc.net/problem/2228 풀이n개의 수로 이루어진 배열에서 m개의 구간을 선택해 각 구간들의 합의 최댓값을 구하는 문제. 단, 구간 사이에는 최소 1의 간격이 있어야한다. dp 이차원 배열을 만들었다. `[수의 번호][구간의 개수]`로 구성했다.for (int k = i; k > 0; k--) { if (k - 2 >= 0) { dp[i][j] = Math.max(dp[i][j], dp[k - 2][j - 1] + sum[i] - sum[k - 1]); } else if (k == 1 && j == 1) { dp[i][j] = Math.max(dp[i][j], sum[i]); }} k번째 원소를 보면서 k번째 원소가 포함되.. 2024. 6. 27. [백준] 1117: 색칠 1 - JAVA https://www.acmicpc.net/problem/1117 풀이W x H 크기의 종이를 가로로 f지점에서 접어 왼쪽이 오른쪽 위로 올라오게 접는다. 그 후 세로로 (c + 1) 등분한다. (x1, y1), (x2, y2)의 지점에 색칠을 하는데, 이 때 겹쳐있는 부분 모두 색칠된다. 색칠이 안된 부분의 크기를 구해야 한다. 처음에는 W x H크기의 배열을 만들어 접는 식으로 구현했다. 이 방법으로 정답은 나왔지만 제출하니 메모리 초과가 발생했다. 그래서 배열을 만들지 않고 바로 뺄 수 있지 않을까 생각했다. 먼저 가로로 접히는 부분을 구해줘야 한다. f가 W / 2보다 크다면 왼쪽 부분이 더 길어져 색칠할 때 오류가 생긴다. 따라서, f가 W/2보다 클 때는 접히는 부분을 W - f로 설정해주었다.. 2024. 6. 25. [백준] 30960: 조별 과제 - JAVA https://www.acmicpc.net/problem/30960 풀이N명의 학생들의 조를 편성해야한다. 1개의 조만 3명으로 편성되고 다른 조들은 2명으로 편성된다. 학생에게 숫자가 부여되는데 각 조 안에서 (최댓값 - 최솟값)이 해당 조의 어색함이 된다. 어색함의 합의 최소가 되도록해야한다. 먼저 입력받은 배열을 정렬했다. 정렬 후 2개의 배열을 만들어서 하나는 앞에서부터 시작, 하나는 뒤에서부터 시작하여 누적합을 담았다. 누적합은 어색함들의 합을 더해줬다. `left[i] += (arr[i] - arr[i-2])` 이런식으로 어색함을 더해줬고, i는 2찍 증가시키면서 진행했다. 누적합 배열 2개를 만든 후, 어느 지점에서 3명인 조를 시작해야 어색함이 최소가될지 구해줬다. 메모리: 84096K.. 2024. 6. 25. [백준] 23889: 돌 굴러가유 - JAVA https://www.acmicpc.net/problem/23889 풀이마을들이 일자로 배치되어있고 돌은 벽을 만날때까지 왼쪽에서 오른쪽으로 굴러간다. 마을에는 모래성이 있어서 돌이 굴러가면 모래성이 다 부서진다. 벽을 세워 돌을 막을 수 있는데 모래성이 가장 적게 부서지게 세워야 한다. 돌의 위치와 몇개의 모래성을 부수는지 이차원배열에 담았다. 먼저 돌이 굴러가기 시작하는 위치를 배열에 넣고, 돌의 위치를 기준으로 다음 돌까지 모래성의 개수를 합하여 배열에 넣었다. 부수는 모래성의 개수를 기준으로 내림차순 정렬하고, 가장 많은 모래성을 지킬 수 있는 경우가 두 가지 이상 존재할 경우, 사전순으로 가장 빠른 답을 출력해야 하므로 모래성의 개수가 같을 경우 돌의 위치를 기준으로 오름차순 정렬하였다. 벽의 .. 2024. 6. 20. 이전 1 2 3 4 5 ··· 25 다음