본문 바로가기

알고리즘/백준126

[Java] BOJ 5557번 1학년 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int N; public static int[] arr; // 결과가 2^63 - 1 이하라는 것을 주의 public static.. 2021. 6. 1.
[Java] BOJ 15683번 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 카메라의 위치를 리스트를 통해 기억해두고 순열을 사용해 각 카메라마다의 방향을 정했습니다. 그 다음 기존 배열은 다음에 완성된 순열에서 사용해야하므로 배열을 복사하여 카메라를 방향과 타입에 맞게 회전시키며 모든 카메라의 감시 위치를 복사한 배열에 저장했습니다. 마지막으로 앞서 저장한 카메라의 감시 위치를 사용해 사각지대의 최소크기를 구하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOEx.. 2021. 5. 31.
[Java] BOJ 17471번 게리맨더링 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 DFS를 사용해서 1번 선거구와 2번 선거구로 나누고 연결을 시켜 만약 연결이 안 된 지역이 있거나 모든 지역이 하나의 선거구로 이루어져 있다면 불가능한 방법이므로 이 경우를 제외한 인구의 최솟값을 구하게 하여 해결했습니다. 이때, 인구의 최솟값은 양수로 출력되야하므로 abs 즉, 절대값을 사용했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp.. 2021. 5. 30.
[Java] BOJ 1600번 말이 되고픈 원숭이 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 BFS를 이용해서 해결했습니다. 이때, 한칸씩 움직이는 경우와 말처럼 움직이는 경우를 전부 구해야합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public.. 2021. 5. 28.
[Java] BOJ 14502번 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 DFS를 사용해서 벽을 둘 수 있는 모든 경우를 조사하고 벽 3개를 모두 세웠다면 배열을 복사한 후 DFS를 이용하여 바이러스를 퍼트리게 했습니다. 다음으로 DFS가 끝나면 바이러스가 퍼지지 않은 영역을 조사해서 안정 영역의 최댓값을 갱신하게 하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Linke.. 2021. 5. 27.
[Java] BOJ 16985번 Maaaaaaaaaze 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 풀이 순열을 이용해 각 층에 넣을 판을 선택하고 5개의 판이 전부 선택됬다면 DFS를 사용해 각 판을 회전시켰습니다. 다음으로 회전이 될때마다 3차원 BFS를 수행하여 목적지로 갈 수 있는지 확인하고 최소 이동횟수를 갱신하게하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util... 2021. 5. 27.

티스토리툴바