Algorithm

[백준, Java] 5557번 : 1학년

🔗 문제 링크 https://www.acmicpc.net/problem/5557 😮 문제 해결 방법 처음부터 숫자를 더하거나 빼면서 그 값이 0이상 20이하가 되어야 한다. 완전탐색으로 문제를 풀기에는 경우의 수가 무수히 많기 때문에 DP를 이용한다. dp 배열의 사이즈는 마지막 숫자를 제외한 숫자의 개수, 0 - 20까지 경우의 수를 저장하게 dp[N-1][21]로 지정한다. 마지막 숫자는 수식의 = 이되기 때문에 마지막 숫자는 배열에서 제외한다. 배열에는 매 인덱스 별 계산한 결과값의 경우의 수가 저장되어있다. 따라서, N-1 인덱스까지 숫자의 인덱스를 옮겨가면서 이전 인덱스까지 결과값 0에서 20까지의 경우의 수 중 1번 이상 결과가 나온 값을 더하거나 빼준다. 더하거나 빼준 값이 다시 0이상 20..

[프로그래머스, Java] 땅따먹기

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12913 😮 문제 해결 방법 간단한 DP문제이다. 현재 스텝의 열에서 최대의 점수를 얻기 위해선 이전 스텝까지의 열 중에서 현재 내가 밟고 있지 않은 열의 최대 점수값을 더해준다. 만약 2번째 스텝의 1번째 열의 최대값을 구하고 싶다면, 1번째 스텝까지의 2,3,4열의 최대값에 현재 밟은 칸의 점수를 더해주면 최댓값이 된다. 이러한 방식을 통해 점화식을 세우면 dp[step][열] = arr[step][열] + max(dp[step-1][열에 해당하지 않는 열])이 된다. dp[step-1][열에 해당하지 않는 열]의 경우 열이 4개가 있기 때문에 max안에 들어가는 dp의 개수는 3개..

[프로그래머스, Java] 방문 길이

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49994 😮 문제 해결 방법 좌표를 하나의 행렬로 이용하기 위해서 10 * 10지도를 11 * 11 좌표로 변환해서 사용했다. 첫 시작 위치는 (5,5)에서 시작하고 상, 하, 좌, 우로 이동하는 경우에 해당 경로를 이용했음을 체크해주는 배열을 생성한다. 배열은 3차원 배열을 사용해 좌표의 행렬과 방향을 표시한다. 3차원 배열을 이용함으로 써 이미 방문한 좌표의 경우에도 방향이 다르면 새로운 경로임을 판단할 수 있다. 이 부분에서 키 포인트는 만약 A → B로 이동하는 경우가 새로운 경로라면, B → A로 이동하는 경로 또한 동일한 경로이기 때문에 체크를 해주어야 하는 것이다. 주어진 ..

[프로그래머스, Java] 주차 요금 계산

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/92341 😮 문제 해결 방법 Map을 이용해서 자동차 번호별 자동차의 정보를 저장한다. 자동차는 차량번호, 주차시간 (주차장 이용시간), 입차 시간, 입/출차 상태를 갖도록 클래스를 만들었다. 먼저 record배열을 하나씩 보면서 자동차의 정보를 Map으로 관리한다. 자동차가 처음으로 입차하는 경우는 containsKey를 이용해 판단하고, 주차시간을 0으로 하고, 입/출차 상태를 false로 넣어준다. 자동차가 출차되는 경우는 출차 시간에서 입차 시간을 빼서 주차시간을 갱신한다. 자동차가 다시 입차되는 경우는 입차 시간을 갱신한다. 모든 이력을 이용해 저장했다면, Map정보를 이용해 ..

[백준, Java] 5186번 : 파티를 열어라!!!

🔗 문제 링크 https://www.acmicpc.net/problem/5186 😮 문제 해결 방법 최대한 많은 차를 이용해 최대한 많은 친구들을 집에 보내줘야 최소한으로 집에서 재울 수 있다. 최대한 많은 친구들을 보내야하기 때문에 “차의 좌석수가 많은 순으로 내림차순" 정렬을 했다. 또한, 운전할 수 있는 친구들을 먼저 배치해주기 위해서 술을 마시지 않은 (S)기준으로 정렬했다. 자동차의 경우 우선순위 큐를 이용해 하나씩 빼면서 태울 수 있는 운전자를 배치한다. 배치된 운전자는 차에 탔다는 체크(ride)를 해주고 운전자 인원수를 1 증가시킨다. 운전자가 배치되는 경우 “태울 수 있는 좌석 - 1 (운전자)”를 지역별 태울 수 있는 인원수 배열(avilable)에 저장한다. 최대한 많은 운전자를 배치..