[백준 10272] 현상금 사냥꾼 김정은 [Java]

문제http://boj.ma/10272 10272번: 현상금 사냥꾼 김정은 boj.ma요약모든 점을 한 번씩만 방문x좌표는 중복되지 않는다.x좌표가 증가하는 순서로 가장 오른쪽 점까지 이동 후 감소하는 순서로 시작점으로 복귀하는 최단 거리를 구하자.풀이 과정아이디어x 좌표가 증가하는 순서로 가장 오른쪽 점까지 이동한 뒤, x 좌표가 감소하는 순서로 시작점(가장 왼쪽 점)으로 돌아오면서, 모든 점을 정확히 한 번씩만 방문하는 비토닉(bitonic) 외판원 순환 문제다.처음에는 가장 왼쪽 점($L$)과 오른쪽 점($R$)을 잇는 선분을 기준으로 점들을 위·아래로 나누는 방법을 생각할 수 있다. 이 경우 비토닉 경로를 만들 수는 있으나, 점들의 실제 거리 관계를 반영하지 못해 항상 최적의 경로를 보장하지 않는..

문제http://boj.ma/2643 2643번: 색종이 올려 놓기 boj.ma 풀이문제 요약N개의 직사각형 종이를 자신보다 크거나 같은 종이 위에만 쌓아 가장 높게 쌓을 때의 높이를 구하자.아이디어종이는 서로의 변에 대해 평행하게만 놓을 수 있으므로 (작은 변의 길이, 큰 변의 길이)를 기준으로 입력받고, 오름차순으로 정렬하자.public class Main { private static class Point { int x, y; public Point(int x, int y) { this.x = Math.min(x, y); this.y = Math.max(x, y); } } A.sort((a, b) -> { if (a.x == b.x) { return Integer.compar..

문제http://boj.ma/12026 12026번: BOJ 거리 boj.ma 풀이문제 요약문자 ‘B’, ‘O’, ‘J’로만 이루어진 문자열에서 규칙을 준수하며 문자열의 처음부터 끝까지 이동하기 위한 최소 비용을 계산하자.아이디어문자열의 길이가 최대 1e3이므로 $O(N^2)$으로 풀이할 수 있다.점화식은 다음과 같다.dp[i] : i번째 보도 블록에 이동하기 위한 최소 에너지 양(도달하지 못하면 -1)i - 1 ~ 0번 블록 중 i번 보도 블록으로 점프할 수 있다면, 이전 블록 + 거리의 제곱의 값과, dp[i]를 비교해 최솟값을 저장하면 된다. // Solve if (A[0] != 'B') { System.out.println(-1); ..

문제http://boj.ma/33941 33941번: 잔돈 싫어 boj.ma 풀이문제 요약조건을 만족하는 환불 가능한 교통 카드의 금액의 최대 합이 500으로 나누어 떨어지도록 적절하게 선택해야 한다.아이디어500으로 나누어 떨어지는 최대 합을 구해야 하므로, 환불 가능한 교통 카드의 금액을 500으로 나눈 나머지와, 환불 비용 500원을 제외한 금액에 대한 배낭문제로 볼 수 있다.점화식은 다음과 같다.dp[n][i]: n번째 환불 가능한 카드들의 잔액 합을 500으로 나눈 나머지가 i가 되는 환불 금액의 최대 합n - 1번째 상태 까지만 필요하므로 다음과 같이 축약할 수 있다.dp[i]: 환불 가능한 카드들의 잔액 합을 500으로 나눈 나머지가 i가 되는 환불 금액의 최대 합 long[] ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-max-coin-change/description 최대 동전 거슬러주기 설명 | 코드트리최대 동전 거슬러주기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약종류 N개의 동전을 최대한 많이 사용해서 M을 만들자.아이디어금액 M에서 coin[j]을 뺀 금액을 만들 수 없는 경우가 존재한다. 이를 유의하며 coin[j - 1]를 만드는 수를 이용해 coin[j]를 만드는 수를 구하자.점화식은 다음과 같다.dp[i] : i를 만들기 위해 사용된 동전의 최대 갯수dp[i] = max(dp[i],..

문제http://boj.ma/29756 29756번: DDR 체력 관리 boj.ma 풀이문제 요약최대 체력 100이고 매 구간마다 선택 여부에 관계없이 K씩 회복할 때, N개의 구간에 대해 최대 점수를 구하자.아이디어(H, S)에 대한 냅색문제다. i구간에서 체력이 부족하면 체력을 회복하고, 해당 구간을 포기해야 한다. 점화식은 다음과 같다.dp[i][h] : 1 ~ i구간에 대해 체력이 h일 때 얻을 수 있는 최대 점수체력이 부족할 때 : dp[i][h] = dp[i - 1][nextH]체력이 충분할 때 : dp[i][h] = max(dp[i - 1][nextH], dp[i - 1][nextH - H[i]] + S[i]) int[][] dp = new int[N + 1][101]; ..