문제링크: https://www.acmicpc.net/problem/12851태그: bfs 풀이 숨바꼭질 문제와 동일하지만, 다른 점이 있다면 이미 방문한 지점도 재방문이 가능하도록 해야한다는 것입니다.재방문이 가능한 기준은 이전에 방문했던 시간과 다시 방문하려고 할때의 도달 시간이 같을 때입니다.다시 방문하려고 할때, 이전에 도달했던 시간보다 크다면, K에 도달했을 때 최단 시간이 될 가능성이 없기 때문에 제외시켜줍니다. vis 배열을 선언해주고 이를 모두 최대값으로 초기화 해준 다음, vis[next] 전체 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;class Main { public stat..

https://www.acmicpc.net/problem/12904  풀이S가 T가 될 수 있는지를 따지지 않고 T가 S가 될 수 있는지를 따지면 되는 문제였다.T가 S가 될 수 있는지를 따지면 경우가 딱 두가지로 나뉜다. (i) T가 A로 끝남 => T의 맨 뒤에 있는 A를 떼면된다.(ii) T가 B로 끝남 => T의 맨 뒤에 있는 B를 떼고 문자열을 뒤집는다. 위 두 경우의 연산을 T와 S의 길이가 동일해질 때까지 반복해주면 된다. 오랜만에 StringBuilder를 써보니까 메소드들이 잘 기억나지가 않았다.delete(시작인덱스, 끝인덱스), reverse(), charAt() 정도는 꼭 기억해두자전체 코드import java.io.BufferedReader;import java.io.InputSt..

문제 풀이이 문제는 knapsack으로 풀 수 있는 문제인데, 그렇게 하기 위해서는 행의 인덱스는 사탕의 번호를, 열의 인덱스는 현재까지 쓴 비용을 나타내도록 하는 배열을 선언해주어야 합니다.그런데 이 문제의 경우, 비용이 소수 2자리까지 있는 실수로 입력되므로, 100을 곱해서 정수로 바꿔서 문제를 해결했습니다.즉, n: 사탕의 종류, m: 비용, M: m에 100을 곱한 수라고 한다면dp[n][M]에는 n번째 사탕까지 고려했을 때, M원을 썼을 때에 최대 칼로리가 담기게 됩니다. 1. 입력 받기int n, m;StringTokenizer st = new StringTokenizer(br.readLine());n = Integer.parseInt(st.nextToken());m = (int)Math.r..

문제풀이1. 입력 받고 정렬하기N개의 집 위치와 사람 수를 입력 받아 List 자료구조에 저장합니다.N = Integer.parseInt(br.readLine());List list = new ArrayList();long slope = 0;for(int i=0; i집의 위치가 오름차순으로 들어온다는 보장이 없으므로, 집의 위치를 기준으로 리스트를 정렬해줍니다.list.sort((a, b) -> { return a[0] - b[0];});2. 언제가 최대일까?문제의 예제 입력을 기준으로 생각해보겠습니다.이 상황에서 우체국이 세워지는 위치를 x라고 한다면, "각 사람들까지의 거리의 합"은 아래 식과 같습니다.그렇다면 이 그래프의 값이 최소가 되는 지점을 찾으면 됩니다.x에 가능한 모든 수를 대입해보면 되..

문제 풀이파라매트릭 서치(매개변수 탐색) 문제입니다.이분탐색으로 값의 범위를 좁혀나가면서 현재 값이 문제의 조건을 만족하냐 만족하지 않느냐를 판단해주면 됩니다.1. 입력받기N = Integer.parseInt(st.nextToken());T = Integer.parseInt(st.nextToken());arr = new int[N][2];for(int i=0; iarr은 (N x 2) 2차원 배열로 다음의 값이 저장됩니다.arr[i][0]: Li. 즉 i번째 사람이 기분 좋아지려면 마셔야하는 최소 술의 양arr[i][1]: Ri. 즉 i번째 사람이 천국에 가지 않는 최대 술 양2. 파라매트릭 서치우선 큰 틀은 아래와 같이 이분탐색 로직입니다.while문 안에는 mid(=구해야하는 S값)가 조건에 맞는지를..

문제문제 링크풀이이 문제는 (0, 0) ~ (N-1, N-1)로 가는데 검은 방을 흰 방으로 최소한으로 바꾸면서 갔을 때, 방 색을 바꾼 횟수를 구하는 문제입니다.즉, 방의 색을 바꾸는 횟수를 가중치로 생각했을 때, 가중치를 최소화하면서 끝 방까지 가는 경우를 구하면 됩니다.만약 일반 bfs처럼 푼다면 (N-1, N-1)에 가장 먼저 도달했을 때 방의 색을 바꾼 횟수가 최소가 아닐 수 있습니다.예시: 아래의 경우, 방 색을 전혀 바꾸지 않고도 끝 방에 갈 수 있지만, 방문하는 순서에 따라 방 색을 바꾸는 루트로 가장 먼저 N-1, N-1에 도달할 수 있음따라서 이 문제에서는 흰 방으로 이동하는 것은 가중치가 0, 검은 방으로 이동하는 것은 가중치가 1이고 큐에 그 칸의 정보를 넣었을 때 가중치가 더 작은..