본문 바로가기

Algorithm221

[백준] 9576: 책 나눠주기 - JAVA https://www.acmicpc.net/problem/9576 풀이이분 매칭 알고리즘을 이용해 풀 수 있는 문제였다. ArrayList에 학생마다 배정할 수 있는 책들을 저장한다. 책의 주인을 담을 수 있는 배열을 만들고, 방문 처리를 할 배열을 만들었다. m명의 학생을 탐색하면서 dfs를 하는데 배정되지 않은 책의 경우 해당 학생에 배정하고, 배정된 경우 해당 책의 주인으로 등록된 사람을 dfs탐색하여 다른 책에 배정할 수 있는 지 확인하고 가능할 경우 새로 배정한다.  메모리: 100992KB시간: 1064ms언어: Java 11import java.util.*;import java.io.*;public class Main { static ArrayList> list; static bo.. 2024. 5. 16.
[백준] 2188: 축사 배정 - JAVA https://www.acmicpc.net/problem/2188 풀이이분 매칭 알고리즘으로 푸는 문제였다. 소가 각각 희망하는 축사 번호가 주어진다. 이것을 `ArrayList>` 에 저장했다. 그 후 1번 소부터 n번 소까지 dfs탐색을 하는데 이때 각 소가 희망하는 축사의 번호를 반복 탐색으로 체크하여 이미 축사가 선점되었으면 그 축사의 주인이 되는 소를 찾아 다른 축사에 들어갈 수 있는지 판단하는 과정을 거친다. 해당 번호의 소가 축사를 배정받을 수 있었다면 카운트를 1늘려준다.  메모리: 17364KB시간: 252ms언어: Java 11import java.util.*;import java.io.*;public class Main { static ArrayList> list; stat.. 2024. 5. 16.
[백준] 19238: 스타트 택시 - JAVA https://www.acmicpc.net/problem/19238 풀이빈칸과 벽이 있는 지도가 주어진다. 택시의 시작위치와 승객의 출발지와 도착지가 주어진다. 택시는 한칸 이동할 때 연료 1씩 소모하며, 승객을 태우고 이동하여 목적지에 도달하였다면 승객을 태우고 이동한 만큼의 2배 연료를 획득한다. 이동하는 중에 연료가 다 떨어지면 끝난다. bfs탐색을 통해 택시로부터 승객까지 최소 위치를 구했고, 다시 bfs탐색으로 승객을 목적지까지 이동시켰다. 택시가 승객에 도착하거나, 목적지에 도착했을 때, 연료 체크를 하여 도중에 0이 되었는지 확인했다.  메모리: 22748KB시간: 220ms언어: Java 11import java.util.*;import java.io.*;public class Main {.. 2024. 5. 16.
[백준] 1749: 점수따먹기 - JAVA https://www.acmicpc.net/problem/1749 풀이n \* m 행렬에서 직사각형의 구간을 잡아 구간의 합의 최대값을 구하는 문제이다. 입력을 받으면서 n \* m 행렬을 누적합으로 저장했다.board[i][j] = Integer.parseInt(st.nextToken()) + board[i - 1][j] + board[i][j - 1] - board[i - 1][j - 1];탐색을 해서 최댓값을 구해야 하는데 구간의 길이가 정해져 있지 않으므로 행시작/끝, 열시작/끝 4중for문을 통해 탐색해야 한다. 열 시작을 rs, 끝을 re, 행 시작을 cs, 끝을 ce로 하여 정답을 갱신했다.ans = Math.max(ans, board[re][ce] - board[rs - 1][ce] - b.. 2024. 5. 16.
[백준] 2955: 스도쿠 풀기 - JAVA https://www.acmicpc.net/problem/2955 풀이숫자 하나를 골라 가로, 세로, 3*3박스를 체크하는 cross-hatching 방법으로 스도쿠를 채우는 문제였다. boolean 배열을 통해 가로, 세로, 박스를 체크해놓고 박스가 false인 구간들을 다시 가로, 세로를 이용해 체크했다. 모순이 일어나는 경우도 체크하여 에러임을 표시했다. 코드 작성 중 오타로 인해 시간이 오래 걸린 문제였다.  메모리: 14204KB시간: 128ms언어: Java 11import java.io.*;public class Main { static int[][] board; static boolean error = false; public static void main(String[] .. 2024. 5. 16.
[백준] 14461: 소가 길을 건너간 이유 7 - JAVA https://www.acmicpc.net/problem/14461 풀이격자로 이루어진 땅을 건너가야하는데 세칸을 이동할 때 마다 격자에 써있는 만큼의 풀을 먹어야 한다. 한칸을 이동할 때는 T만큼의 비용이 든다. 격자 칸마다 다른 가중치가 있다. 즉, 다익스트라를 이용해 문제를 풀면 된다. 3칸을 이동하는 방법은 ABA 처럼 갔던 칸에 다시 방문하는 방법이 있고, ABC처럼 다른 칸에 갈 수도 있다. 이러한 방법들을 적어보니 16가지가 된다. 이차원 배열로 만들어 사용했다.static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 3, 0 }, { -3, 0 }, { 0, 3 }, { 0, -3 }, { 2, 1 },.. 2024. 5. 16.
[백준] 15824: 너 봄에는 캡사이신이 맛있단다 - JAVA https://www.acmicpc.net/problem/15824 풀이매운 정도를 배열로 입력받아 몇 개를 선택하여 조합을 만들 경우 그 안에서 최댓값과 최솟값의 차이가 그 조합의 맛의 정도가 된다. 이런 맛의 정도들의 합을 구하는 문제이다. 먼저 입력받은 배열을 정렬했다. i번째 인덱스의 경우 이 값이 최솟값이 되는 경우는 2^i개의 경우, 이 값이 최댓값이 되는 경우는 2^(N - i - 1)개의 경우가 된다. 2의 거듭제곱을 구하기 위해 분할정복을 이용했다.  메모리: 58472KB시간: 792ms언어: Java 11import java.util.*;import java.io.*;public class Main { static final int MOD = 1_000_000_007; st.. 2024. 5. 16.
[백준] 13334: 철로 - JAVA https://www.acmicpc.net/problem/13334 풀이n명의 사람에 대해 2개씩 점의 위치가 주어지고, d길이의 선을 위치했을 때 2개의 점이 모두 선 안에 있는 사람의 최댓값을 구하는 문제이다. 입력을 받으면서 우선순위큐에 저장했다. 우선순위큐의 정렬 조건은 오른쪽 점을 오름차순으로, 오른쪽 점이 같을 경우 왼쪽 점을 오름차순으로 했다. 또 다른 우선순위큐을 만들어 개수를 세는 용도로 사용했다. 첫번째 우선순위큐를 pq라 하고, 두번째 우선순위큐를 count라고 했다. pq에서 값을 빼서 count에 넣는다. 이때 선분 d의 오른쪽 점을 pq에서 뺀 값의 오른쪽 점으로 하고, 이 선분에 왼쪽 점이 속해있지 않는 값들을 count에서 뺀다. 그 후 최댓값을 count의 size와 비교하.. 2024. 5. 16.
[백준] 1525: 퍼즐 - JAVA https://www.acmicpc.net/problem/1525 풀이3x3 표의 퍼즐을 맞추는데 최소 이동 횟수를 구하는 문제였다. 빈칸은 0으로 주어지고 0의 상하좌우에 있는 숫자를 0위치로 이동시킨다. 0을 기준으로 상하좌우를 탐색하여 숫자를 바꿔주고, 그렇게 만들어진 배치를 방문처리하였다. 이때 방문처리를 String으로 하였는데, 메모리제한때문이었다. 숫자들을 이어붙여 String으로 만들었고, String의 indexOf 메서드를 이용하여 위치를 찾아 좌표를 구했다. Map에 String과 이동횟수를 저장하며 방문처리를 해줬고, "123456780"이 된다면 퍼즐의 완성이므로 Map에서 이동횟수를 꺼내어 출력했다.  메모리: 122456KB시간: 1048ms언어: Java 11import ja.. 2024. 5. 15.
[백준] 14867: 물통 - JAVA https://www.acmicpc.net/problem/14867 풀이용량이 정해진 물통을 주어진 용량으로 맞춰야 한다. 할 수 있는 동작은 정해져있는데 1. 물통 x에 물을 가득 채운다. 2. 물통 x의 물을 모두 버린다. 3. 물통 x의 물을 물통 y에 붓는다. 위의 세가지를 통해 용량을 맞출 때 최소 작업 수를 구해야 한다. 두 개의 물통을 0, 0상태에서 시작하여 bfs탐색을 통해 정해진 양을 맞추면 return했다. 이때 방문처리를 하기 위해 class를 만들어 set으로 체크하였다. set의 contains 메서드를 이용할 때 객체의 경우 비교하기 위해서는 class에 equals와 hashcode를 오버라이드해야 했다. 이 점만 알고 있다면 크게 어려운 것 없는 문제였다.  메모리: 146.. 2024. 5. 14.

티스토리툴바