본문 바로가기

문제 풀이19

[백준] 2616번 - 소형기관차 (Java) 문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 알고리즘 다이나믹 프로그래밍 (DP), 누적합 우선, 각 열차의 승객의 누적합을 구해둔다. 계산식을 단순화하여 계산 속도를 빠르게 하기 위함의 목적이다. 그 다음 dp 배열을 세운다. dp[i][j] : 소형 기관차 i개로 j번째 칸까지 살펴봤을 때, 그 시점에서 최대로 운송할 수 있는 손님의 수 예를 들어, 객실 칸이 1~9번까지 있다고 해보자. dp[2][6]은 소형 기관차 2대로 .. 2024. 3. 18.
[백준] 23818번 - 원수의 원수 (Java) 문제 https://www.acmicpc.net/problem/23818 23818번: 원수의 원수 사람의 수 $N \, (2 \leq N \leq 100,000)$과 관계의 수 $M \, (0\leq M \leq 100,000)$, 그리고 대답해야 할 관계의 수 $K \, (1\leq K \leq 100,000)$가 입력으로 들어온다. 그 후 $M$개의 줄에 걸쳐 $t \in \{0, 1\}$, $a$, $b$ $(1 www.acmicpc.net 알고리즘 이분 그래프, 깊이 우선 탐색(DFS) 모든 관계를 저장해두고, DFS로 타고타고 들어가면 된다. DFS로 타고 들어가면서 answer 배열에 관계를 저장해둔다. 이때, 동일한 그래프 내 있는 노드들의 answer 절대값은 동일하다. 예를 들어, 1 .. 2024. 3. 12.
[백준] 27453번 - 귀엽기만 한게 아닌 한별 양 문제 https://www.acmicpc.net/problem/27453 27453번: 귀엽기만 한 게 아닌 한별 양 첫 번째 줄에 마을의 세로 크기 $N$, 가로 크기 $M$, 한별이가 연속해서 막을 수 있는 불상사의 개수 $K$가 주어진다. ($2\leq N,M\leq 1\,000$, $0\leq K\leq 27$) 다음 $N$ 개의 줄에 걸쳐 마을의 상태가 주어진 www.acmicpc.net 입력 출력 알고리즘 너비 우선 탐색(BFS) 꽤 푸는데 고생을 했던 문제였다. 근데 굉장히 아이디어가 재밌는 BFS 문제!! 최근 지나온 3칸의 개수가 k개를 넘는지 확인하면서 최단 거리를 구하는 것이므로 BFS를 돌리면 된다. 여기서 중요한 것이, 최근 지나온 3칸만 보면 되는 것이므로 이미 왔던 칸이라도, .. 2023. 12. 8.
[백준] 23817번 - 포항항 (Java) 문제 https://www.acmicpc.net/problem/23817 23817번: 포항항 첫번째 예제의 경우 오른쪽 3칸, 왼쪽 1칸, 아래쪽 3칸, 오른쪽 1칸, 왼쪽 3칸으로 총 11칸 이동하여 5개의 식당을 방문할 수 있다. 두번째 예제의 경우 장애물에 가로막혀 5개의 식당을 방문할 수 www.acmicpc.net 입력 출력 알고리즘 너비 우선 탐색 (BFS), 브루트포스, 백트래킹 우선 내가 틀렸던 풀이를 하나 소개해보고자 한다. 이 부분은 틀린 풀이입니다. 정답 풀이가 궁금하시면 밑에 봐주세요. 처음에 시도했던 방법은 아래와 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead.. 2023. 12. 7.
[백준] 3015번 - 오아시스 재결합 (Java) 문제 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 입력 출력 알고리즘 스택 참... 어려운 문제다. 혼자서 못풀고 결국 답을 보고 풀었다. 일단 기본적인 프로세스는 다음과 같다. 0. 한명의 학생 키를 받는다. 1. Stack이 비어있으면, 아무것도 하지않고 스택에 학생 키를 집어넣는다. Stack이 비어있다는 말은 쌍을 지어줄 학생이 없다는 의미이기 때문이다. 2. 스택이 비어있지 않으면 2가지 중에서 하나를 수행한.. 2023. 12. 7.
[백준] 1525번 - 퍼즐 (Java) 문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 입력 출력 알고리즘 너비 우선 탐색 (BFS), 해시 맵 (Hashmap) 초기 게임판에서 아래와 같은 정렬된 상태로 만들 수 있는가?를 확인할 것이다. 일단 움직일 수 있는 최소 횟수를 물었으므로, 최단 경로를 물어보고 있는 것이다. 따라서 이 문제는 DFS로 풀 수 없다. 반드시 BFS로 풀어야한다. 그럼 단순하게 생각해본다면, 그냥 현재 게임판 상태 전체를 큐에 같이 넣고 돌리면 되지 않는가?라고 생각할 수 있다. 그런데, 큐에 이 이차원 배열을 통째로 넣고 돌리.. 2023. 12. 6.
[백준] 1202번 - 보석 도둑 (Java) 문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 입력 출력 알고리즘 방법 1 : 그리디 알고리즘, 우선순위 큐 방법 2 : 이분 탐색, 분리 집합 (유니온 파인드) (작성 예정) 코드 [ 방법 1 ] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import j.. 2023. 12. 6.

티스토리툴바