[백준/BOJ] 1202 보석 도둑- JAVA문제https://www.acmicpc.net/problem/1202 문제 분석조건N개의 보석이 각각의 무게와 가격을 가지고 있고, K개의 가방이 각각의 최대 허용 무게를 가지고 있다. 각 가방에는 최대 한 개의 보석만 넣을 수 있을 때, 훔칠 수 있는 보석의 최대 가격을 구하는 문제이다.풀이방법가장 작은 가방부터 넣을 수 있는 보석 중 가장 가치가 큰 보석을 넣는 그리디 방식으로 해결했다.가장 먼저 보석은 무게가 가벼운 순으로, 가방은 담을 수 있는 용량이 작은 순으로 정렬한다.그다음, 용량이 가장 작은 가방부터 순서대로 확인하며 현재 가방에 담을 수 있는 무게의 보석들을 모두 찾아낸다.이렇게 찾아낸 보석들은 정답이 될 수 있는 후보군이므로, 이 보석들의 가..

[프로그래머스] 12907 거스름돈 - JAVA문제https://school.programmers.co.kr/learn/courses/30/lessons/12907 문제 분석조건`n`원을 거슬러 줘야 할 때, 보유하고 있는 동전의 종류 `money`를 이용하여 거슬러 줄 수 있는 방법의 가짓수를 구하는 문제이다.풀이방법DP를 이용해서 조합의 수를 구하는 문제이다. `dp[i]`는 i원을 만들 수 있는 경우의 수이다. `dp[0] = 1`으로 0원을 거슬러주는 방법은 아무동전도 사용하지 않으므로 1가지 방법이 있다. 코드를 기준으로 예제1번을 순차적으로 진행하면 가진 동전의 종류는 `[1, 2, 5]`이고 목표 금액은 5원이다.1. 1원짜리로 만들 수 있는 경우의 수dp = [1, 1, 1, 1, 1, 1..

[백준/BOJ] 20058 마법사 상어와 파이어스톰 - JAVA문제https://www.acmicpc.net/problem/20058 문제 분석조건`(2N)×(2N)` 크기의 격자에 각 칸의 얼음의 양이 주어진다. Q번의 파이어스톰을 시전할때 한번의 파이어스톰은 아래 과정을 거친다.1. 전체 격자를 `(2L)×(2L)`크기의 부분격자로 나누고 모든 부분격자는 시계 방향으로 90도 회전한다.2. 상하좌우로 인접한 칸에 얼음이 있는 칸이 3개 미만이면 해당 칸의 얼음의 양이 1 줄어든다.Q번의 파이어스톰을 모두 시전한 후, 전체 격자에 남아있는 얼음의 총량과 가장 큰 얼음 덩어리가 차지하는 칸의 개수를 출력하는 문제이다.풀이방법단순 구현문제로 부분적으로 격자를 회전시키고 얼음을 녹이는 것을 구현하였다. 남은..

[프로그래머스] 1843 사칙연산 - JAVA문제https://school.programmers.co.kr/learn/courses/30/lessons/1843 문제 분석조건숫자와 연산자(+,-)로 이루어진 배열이 주어진다. 이 식에 괄호를 추가하여 바뀐 연산 순서에 따라 만들 수 있는 최댓값을 구하는 문제이다.풀이방법괄호의 위치에 따라 결과가 달라지므로 모든 경우의 수를 고려해야한다. 왜냐하면 -연산자일 경우 뒷 숫자가 작을수록 결과값을 더 크게 만드는 경우가 있다. 그래서 값을 다루려면 연산 과정에서 최댓값과 최솟값을 동시에 고려해야한다.코드와 예제를 기반으로 설명을 하자면, `maxDp[start][end]` 는 `start`번째 숫자부터 `end`번째 숫자까지 연산 결과 중 최댓값을 의미하고,`m..

[백준/BOJ] 2252 줄 세우기 - JAVA문제https://www.acmicpc.net/problem/2252 문제 분석조건N명의 학생과, 두 학생의 키를 비교한 M개의 정보가 주어진다.키 비교 정보는 `A B`형태로 주어지며, A학생이 B학생보다 앞에 서야 한다는 순서 관계를 의미한다. 이 순서 관계를 모두 만족하도록 학생들을 전체 줄 세우는 문제이다.풀이방법이 문제는 전형적인 위상 정렬 문제이다. A학생이 B학생보다 앞에 선다는 정보를 바탕으로 `A -> B`형태의 간선을 가지는 그래프로 만들어 문제를 해결했다.문제에서 진입차수로 작성한 inDegree는 앞에 서야 되는 학생들의 수를 의미한다.코드import java.io.BufferedReader;import java.io.IOExceptio..

[프로그래머스] 86053 금과 은 운반하기 - JAVA(파라메트릭 서치)문제https://school.programmers.co.kr/learn/courses/30/lessons/86053 문제 분석조건여러 도시에 각각 일정량의 금`g`과 은`s`이 있다. 각 도시의 트럭은 한 번에 특정 무게`w`만큼의 광물을 특정 시간`t`을 들여 편도로 운반할 수 있다. 목표 지점에 금 `a`와 은 `b`를 모두 배달하기 위해 필요한 최소 시간을 구하는 문제풀이방법시간에 따라 트럭을 옮겨가며 계산하기엔 시간이 초과된다. 이 문제는 특정시간`time`동안 목표한 금과 은을 운반할 수 있는지를 확인하며 문제를 풀어야 한다. 이분탐색을 통해 시간을 줄여가며 배달이 가능한 최소 시간을 구하는 문제이다.그리고 이렇게 특정 ..