본문 바로가기

Algorithm6

[Java / 백준] 4781. 사탕 가게 문제 풀이이 문제는 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.. 2024. 7. 3.
[백준 / Java] 2141. 우체국 문제풀이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에 가능한 모든 수를 대입해보면 되.. 2024. 6. 25.
[백준 / Java] 14575. 뒤풀이 문제 풀이파라매트릭 서치(매개변수 탐색) 문제입니다.이분탐색으로 값의 범위를 좁혀나가면서 현재 값이 문제의 조건을 만족하냐 만족하지 않느냐를 판단해주면 됩니다.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값)가 조건에 맞는지를.. 2024. 6. 18.
[백준 / Java] 2665. 미로만들기 문제문제 링크풀이이 문제는 (0, 0) ~ (N-1, N-1)로 가는데 검은 방을 흰 방으로 최소한으로 바꾸면서 갔을 때, 방 색을 바꾼 횟수를 구하는 문제입니다.즉, 방의 색을 바꾸는 횟수를 가중치로 생각했을 때, 가중치를 최소화하면서 끝 방까지 가는 경우를 구하면 됩니다.만약 일반 bfs처럼 푼다면 (N-1, N-1)에 가장 먼저 도달했을 때 방의 색을 바꾼 횟수가 최소가 아닐 수 있습니다.예시: 아래의 경우, 방 색을 전혀 바꾸지 않고도 끝 방에 갈 수 있지만, 방문하는 순서에 따라 방 색을 바꾸는 루트로 가장 먼저 N-1, N-1에 도달할 수 있음따라서 이 문제에서는 흰 방으로 이동하는 것은 가중치가 0, 검은 방으로 이동하는 것은 가중치가 1이고 큐에 그 칸의 정보를 넣었을 때 가중치가 더 작은.. 2024. 6. 11.
[ 백준 / Java ] 2573. 빙산 문제풀이빙하가 모두 녹거나, 빙하가 녹아서 두 부분 이상이 될때까지 반복문으로 빙하 녹이는 과정을 반복하고, 조건을 만족한다면 반복문을 break로 빠져나옵니다. for(int t = 1; ; t++) { // 시간을 계속 증가시키는 무한 반복문 ... }모든 칸을 돌면서 주변 0의 개수를 세어줍니다. (주변 0개수를 removeCnt에 저장)removeCnt의 값을 각 칸에서 빼줍니다. 이때 만약 map[i][j] - removeCnt[i][j]가 음수가 된다면, 0으로 바꿔줍니다.빙하가 모두 녹았는지 확인하고, 다 녹았다면 반복문을 빠져나갑니다.빙하가 몇 부분으로 갈라졌는지 개수를 세어줍니다. 여기서 dfs 로직이 필요합니다.빙하가 모두 녹거나, 2부분이상으로 녹을 때까지 위 로직.. 2024. 6. 4.
[백준 / Java] 2477. 참외밭 문제 풀이1. 클래스, 변수 선언 및 입력 받기Line이라는 클래스를 선언해줍니다.Line 클래스에는 선의 길이와 방향이 들어갑니다. static ArrayList lines; static class Line { int len; int direction; Line(int direction, int len) { this.len = len; this.direction = direction; } } K = Integer.parseInt(br.readLine()); for(int i=0; i 2. 가로, 세로에서 가장 긴 변 구하기입력으로 들어오는 도형은 항상 ㄱ 을 회전시킨 모양이므로, 큰 직사각형에서 작은 직사각형이 빠진 모양입니다.따라서 큰 직사각형의.. 2024. 5. 28.

티스토리툴바