알고리즘 문제 풀이

[백준 14502] 연구소 java

https://www.acmicpc.net/problem/14502 문제 안전 영역이 최대가 되도록 벽 3개를 세웠을 때의 안전 영역 크기 구하기. 0: 빈칸 1: 벽 2: 바이러스 바이러스는 상하좌우 인접한 빈칸으로 퍼져 나갈 수 있으며 벽을 만나면 멈춘다. 문제 예제 2번의 경우 빨간색 위치에 벽을 세우고 나면 바이러스가 초록색 칸들로 퍼진다. 이후 남은 0의 개수는 9개가 된다. 풀이 방법 벽 3개를 세우는 모든 경우에서 안전 영역의 크기를 계산해서 최대 안전 영역의 크기를 계산한다. 벽 3개를 세운다. 바이러스가를 전파 시킨다. 빈칸(안전영역)의 크기를 센다. 코드 처음엔 안전 영역이 여러개 나오면 그 중 가장 큰 안전 영역의 값이 답인줄 알았는데 그런게 아니고 그냥 지도 전체에서 0의 개수만을 ..

[백준 17069] 파이프 옮기기2 java

문제 파이프를 연결해서 (N-1,N-1)칸 까지 갈 수 있는 경우의 수를 세는 문제. 파이프는 세로, 가로,대각선으로만 둘 수 있다. 세로 파이프는 세로, 대각선으로만 이을 수 있다. 가로 파이프는 가로, 대각선으로만 이을 수 있다. 대각선은 가로,세로,대각선 모두 가능하다. 풀이 방법 i,j 좌표로 올 수 있는 방법을 저장하는 3차원 dp배열을 만들어서 저장 한다. 파이프 모양에 따라서 방법의 수가 달라지기 때문에 3차원으로 만들어서 가로,세로,대각선일 경우를 각각 따져야 한다. (i,j)에 두는 파이프 모양에 따라 경우의 수를 구한다. 가로로 둘 경우 - 왼쪽 칸에 가로로 둔 경우, 대각선으로 둔 경우만 가능 : (i,j-1)의 가로 방법 수 + (i,j-1)의 대각선 방법의 수 세로로 둘 경우 - ..

[SWEA 1249] 보급로 java

문제 map을 지날 때 마다 드는 비용이 주어진다. (0,0)에서 (N-1,N-1) 칸으로 이동하는 최소 경로 비용을 찾는다. 풀이 방법 (0,0) 부터 bfs로 경로를 탐색한다. 일반적인 bfs는 visited 여부를 boolean 배열을 만들어서 체크하지만, 이 문제는 한번 간 경로라도 최소 경로가 새로 발견 된다면 다시 탐색한다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class Solution_1249_보급로 { static int N; static int map[]..

[SWEA 5644 ] 무선 충전 java

두 사용자의 1초마다의 이동 경로가 주어진다. 각 초 마다 충전되는 양의 최댓값을 구하는 문제. 풀이 방법 map 을 3차원 배열로 선언 했다. BC마다 충전 가능한 범위를 map에 표시 한다. 예를 들어 BC가 3개일 때 (1,2)위치는 BC 2로도 충전 가능하고 BC3으로도 충전 가능 하다면, map[1][2]={0,0,1,1,0} 이렇게 저장한다. 각 초 마다 사용자 두명 A,B를 이동 시킨다. 사용자가 서로 다른 BC로만 충전이 가능하다면 충전 양을 더해주기만 하면 된다. 문제는 사용자들이 충전 가능한 BC들이 겹쳐서 최대 경우를 따져 주어야 할 때이다. map에 저장 해둔 배열의 값들을 각각 더해보면서 하나라도 2가 나온다면 충전 영역이 겹친다는 의미가 된다. 그런 상황이라면 A,B가 최대로 충..

[백준 1463 ] 1로 만들기 java

문제 정수를 문제에서 주어진 연산만을 통해서 1로 만든다. 1로 만들 수 있는 최소 횟수를 출력한다. 가능한 연산 목록 X가 3으로 나누어 떨어지면 3으로 나눈다. X가 2로 나누어 떨어지면 2로 나눈다. 1을 뺀다. 풀이 방법 1로 만들 수 있는 최소 횟수를 배열에 저장한다. arr[i] 는 i를 1로 만드는 최소 횟수이다. 기본적으로 arr[i] = arr[i-1]+ 1 로 구할 수 있다. i 에 -1 연산을 한번 하면 되기 때문이다. 따라서 기본적으로 arr[i]=arr[i-1]+1 이다. 여기서 i가 2 혹은 3으로 나누어 떨어지면 arr[i/2]+1 혹은 arr[i/3]+1 로 값을 변경한다. Java 코드 import java.util.Scanner; public class Main { pub..