알고리즘/BJ

[BJ] 백준 1753 최단경로(JAVA)

문제 https://www.acmicpc.net/problem/1753 풀이 방법 이 문제는 다익스트라를 이용하는 문제였던걸로 기억한다. 시작 위치에서부터 가장 최소인 경로를 출력하면 된다. 나는 우선 정점과 가중치를 저장하기 위한 클래스를 하나 선언해줬고, 우선 순위큐를 사용했다. 우선순위 큐에는 현재 시작점으로 부터 가장 가중치가 작은걸 우선으로 정렬하도록 선언했다. 우선순위 큐에서 하나씩 꺼내면서 꺼낸걸 방문 체크해주고, 꺼낸걸 기준으로 꺼낸 점접의 인접 점들을 보면서 꺼낸 것을 경유지로 간다면 더 작은 경로인 경우들만 경로를 업데이트 해주고, 우선순위 큐에다가 넣어주는 식으로 구현했다. 제출 코드 import java.io.*; import java.util.*; import sun.securit..

[BJ] 백준 10158 개미(JAVA)

문제 https://www.acmicpc.net/problem/10158 풀이 방법 문제를 간단하게 이해하면 t초후 개미의 위치를 구하면 되는 문제다. 이동은 45도로 이동을 하기 때문에 물론 이동 방향을 사용해서 하면 어려운 문제는 아니다. 하지만 이 문제에서 그런식으로 문제를 푼다면 시간초과가 난다. 시간을 단축시킬 수 있는 다른 방법을 찾아야한다. 나도 처음엔 위와 같은 방식으로 문제를 풀었는데 시간초과가 났고, 어떤 식으로 풀어야할 지 계속해서 고민을 한 것 같다. 몇시간을 고민하면서 시도를 했었는데 도저히 풀리지가 않아서 힌트를 조금 얻어서 풀었다. 내가 본 힌트는 x와 y좌표를 따로 구해보라 였다. 그래서 어떻게 따로 구하지 생각을 하다가 x좌표만 가지고 보니 좌표가 열 길이의 2배만큼 이동을..

[BJ] 백준 10163 색종이(JAVA)

문제 https://www.acmicpc.net/problem/10163 풀이 방법 이 문제는 서브태스크로 채점이되는 문제이다. 서브태스크 문제는 약간 예외를 생각하기 좋은 것 같다. 문제를 간단하게 설명하자면 여러장의 색종이를 순서대로 놓는데 겹쳐서 놓을 수가 있다. 출력값으로 색종이를 다 놓았을 때 각각의 색종이가 보이는 면적을 출력해야한다. (https://yoon990.tistory.com/33 이 문제가 생각이 났다.) 그래서 위에서 언급한 문제를 응용해서 이번에는 무조건 1로만 채우는 것이 아니라 색종이의 번호를 넣어주는 식으로 생각을 했다. 첫번째 색종이 면적은 1로, 2번째면 2로 .. 이런식으로 N번째 색종이까지 다 채운 후, 마지막에 1부터 N까지 map에 자신에 해당하는 번호가 몇 개..

[BJ] 백준 2628 종이자르기 (JAVA)

문제 https://www.acmicpc.net/problem/2628 풀이 방법 우선 행과 열의 크기에 맞게 1차원 배열을 선언해줬다. 그리고 그 배열에는 입력에 따라서 자른 점선 번호이면 1로 배열 값을 수정해줬다. 문제와 같은 예시로 설명을 하자면 num 1 2 3 4 5 6 7 8 9 cutM 0 0 0 1 0 0 0 0 0 num 1 2 3 4 5 6 7 cutN 0 1 1 0 0 0 0 이런식으로 값이 들어가게 된다. 그 후 이제 각각 배열을 돌면서 temp 길이를 1을 하나씩 추가하다가 1을 만나면(잘려진 선을 만났으므로) 최대 길이와 비교해서 필요시 최대길이를 업데이트해주고 temp는 다시 0으로 설정해준다. (새로운 길이 시작) 열과 행을 같은 방법으로 구현 후, 각각의 max값을 곱해주..

[BJ] 백준 15686 치킨배달 (JAVA)

문제 https://www.acmicpc.net/problem/15686 풀이 방법 문제를 보고서 어떤식으로 문제를 풀어야할 지 순서를 생각해봤다. 1. 우선 치킨집에서 어떤 치킨집을 남겨둘 것인지에 대한 조합 만들기 2. 골라진 치킨집들을 가지고 치킨거리를 구하기 3. 치킨 거리를 구하면서 최소값 저장하기 순서로 구현했다. 제출 코드 import java.io.*; import java.util.*; public class BJ_15686_치킨배달 { public static int N, M, minDist; public static int[] chickenDist; public static int[][] map; public static int[][] selectChicken; public stati..

[BJ] 백준 2635 수 이어가기 (JAVA)

문제 https://www.acmicpc.net/problem/2635 풀이 방법 첫 번째 수를 입력으로 받고 두번째 수를 선택한 뒤 세번째 부터는 앞에 두 개의 숫자를 빼면서 하나씩 새로운 수를 만들어가는 문제이다. 1. N 부터 1 까지 하나씩 두번째 수로 선택 한다. 2. 음수가 나올때까지 while문에서 세번째 수 부터 하나씩 만들면서 list에 추가한다. 3. 하나의 list가 만들어질 때마다 최대 크기를 비교해서 업데이트하고, 업데이트가 되는 경우엔 배열도 같이 복사해준다. 3. 마지막엔 최종적으로 max에 담겨있는 개수와 list를 출력해줬다. 제출 코드 import java.io.*; import java.util.*; public class BJ_2635_수이어가기 { public sta..

[BJ] 백준 2304 창고 다각형 (JAVA)

문제 https://www.acmicpc.net/problem/230 풀이 방법 여러개의 기둥들이 있고, 그 위에 지붕을 만드는 문제이다. 문제의 포인트는 오목한 부분이 없어야하는 것이다. 그래서 나는 가장 높은 기둥을 찾고, 그 전과 후를 따로 계산했다. 우선 기둥들의 정보를 저장하고 정렬할 때 필요한 compareTo 함수를 재정의 해줬다. 기둥들의 순서가 순차적으로 들어오지 않기 때문에 정렬을 사용했다. 가장 높은 기둥을 기준으로 앞부분에서는 현재 기둥보다 더 높은 기둥이 올 때만 값을 더해주고 뒷부분은 끝에서부터 오면서 더 높은 기둥이 올 때만 값을 더해주는 식으로 구현했다. 제출 코드 import java.io.*; import java.util.*; public class BJ_2304_창고다..

[BJ] 백준 15683 감시 (JAVA)

문제 https://www.acmicpc.net/problem/15683 풀이 방법 cctv의 종류에 따라서 탐색해야하는 방향이 다른 문제이다. cctv가 탐색할 수 있는 공간을 다 탐색 후 cctv가 탐색하지 못한 사각지대를 찾아내면 된다. 복잡하긴 하지만 정리해서 구현만 한다면 그렇게 어렵지는 않은 문제다. 1. 클래스를 하나 만들어서 cctv의 종류에 따라서 탐색해야하는 인덱스를 미리 저장해놨다. 2. cctv의 종류에 따라서 방향이 다르기도 하지만 탐색 횟수도 다르다는걸 주의해야한다. ex) 1번은 90씩 회전해서 4번 탐색이 가능하지만, 2번은 2번만 탐색한다. 3. 탐색을 하면 나는 #으로 배열을 변경해줬고, 나중에 사각지대를 계산할 때는 0인 것들을 찾아서 카운팅 한 후 출력해줬다. 제출 코..

[BJ] 백준 1244 스위치 켜고 끄기 (JAVA)

문제 https://www.acmicpc.net/problem/1244 풀이 방법 스위치의 상태를 바꿔주는 문제이다. 여학생인지 남학생인지 판단 후에 남학생이라면 해당 번호의 배수에 해당하는 인덱스를 가진 스위치를 토글해주고, 여학생이라면 해당 번호의 스위치를 우선 변경 후 , -1 +1를 위치에 있는 스위치가 같은지 여부를 판단 후, 같다면 토글해주고 같지 않다면 토글하지 않는 식으로 구현했다. 제출 코드 import java.io.*; import java.util.*; public class BJ_1244_스위치켜고끄기 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(..