Yepchani's place

[BOJ 16234] 인구 이동

문제인구 이동https://www.acmicpc.net/problem/16234  풀이설명인구 이동이 며칠 동안 발생하는지를 구하는 문제입니다. 규칙은 다음과 같습니다.국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 엽니다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작합니다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 합니다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 됩니다. 편의상 소수점은 버립니다. 연합을 해체하고, 모든 국경선을 닫습니다. 그래프 탐색을 이용해 해결할 수 있습니다. 예시 코드funct..

[BOJ 1202] 보석 도둑

문제보석 도둑https://www.acmicpc.net/problem/1202  풀이설명훔칠 수 있는 보석 가격의 합의 최댓값을 구하는 문제입니다. 그리디 알고리즘과 우선순위 큐를 사용해 해결할 수 있습니다. 보석은 무게를 기준으로 오름차순, 가방은 오름차순으로 정렬합니다. 가방을 순회하면서 현재 가방에 담을 수 있는 모든 보석을 큐에 추가합니다.큐에는 가방에 담을 수 있는 보석들이 가격이 비싼 순으로 들어 있습니다.큐 추가 작업이 끝나면 가장 비싼 보석을 꺼내 결과에 더해줍니다. 예시 코드function solution() { const [n, k] = input().split(" ").map(Number); const gems = Array.from({ length: n }, () => input..

[BOJ 13023] ABCDE

문제ABCDEhttps://www.acmicpc.net/problem/13023  풀이설명조건에 맞는 A, B, C, D, E가 존재하는지를 구하는 문제입니다. DFS를 이용해 해결할 수 있습니다. 주어진 관계를 토대로 그래프를 구성한 후, 각 노드를 순회하며 dfs를 진행해 조건을 만족하는지 확인하면 됩니다. 예시 코드function solution() { const [n, m] = input().split(" ").map(Number); const visited = Array(n).fill(false); const graph = Array.from(Array(n), () => []); let result = false; for (let i = 0; i

[BOJ 16236] 아기 상어

문제아기 상어https://www.acmicpc.net/problem/16236  풀이설명아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 구하는 문제입니다. 규칙은 다음과 같습니다.아기 상어의 처음 크기는 2이고, 1초에 상하좌우로 인접한 한 칸씩 이동 가능합니다.자신보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있습니다.이동한 칸에 자신보다 크기가 작은 물고기가 있다면 먹을 수 있습니다. 물고기를 먹으면 그 칸은 빈 칸이 됩니다.아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가합니다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 됩니다. 이동 우선순위는 다음과 같습니다.가장 가까운 물고..

[BOJ 11660] 구간 합 구하기 5

문제구간 합 구하기 5https://www.acmicpc.net/problem/11660  풀이설명(x1, y1)부터 (x2, y2)까지 합을 구하는 구하는 문제입니다. DP를 이용해 해결할 수 있습니다. dp[i][j]는 (1, 1)부터 (i, j)까지의 합입니다. 점화식은 다음과 같습니다.dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] 예시 코드function solution() { const [N, M] = input().split(" ").map(Number); const board = Array.from({ length: N }, () => input().split(" ").map(Number)); const dp = A..

문제스티커https://www.acmicpc.net/problem/9465  풀이설명있는 스티커 점수 합의 최댓값을 구하는 문제입니다. DP를 이용해 해결할 수 있습니다. dp[i][j]는 (i, j)번째 스티커를 골랐을 때 얻을 수 있는 점수 합의 최댓값입니다. 스티커의 점수를 저장한 n * 2 크기의 배열을 stickers라고 할 때,점화식은 다음과 같습니다.dp[i][j]는 다음 두 값중 더 큰 값에  stickers[i][j]를 더한 값입니다.dp[i - 1][1 - j]dp[i - 2][1 - j] 예시 코드function solution() { const T = Number(input()); const answer = []; for (let tc = 0; tc input().s..

문제포도주 시식https://www.acmicpc.net/problem/2156  풀이설명마실 수 있는 포도주의 최대 양을 구하는 문제입니다. 규칙은 다음과 같습니다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 합니다.연속으로 놓여 있는 3잔을 모두 마실 수는 없습니다. BOJ 2579번 계단 오르기 문제와 유사하나, 계단 오르기 문제와 달리 마지막 잔을 꼭 선택할 필요는 없습니다. 마찬가지로 DP를 이용해 해결할 수 있습니다. dp[i]는 i번째 포도주 잔이 마지막 잔일 때 마실 수 있는 최대 양입니다. 포도주의 양을 담은 배열을 wines라고 할 때,dp[i]의 값은 다음 세 가지 중 가장 큰 값입니다.dp[i - 1]dp[i - 2] + ..

문제뱀https://www.acmicpc.net/problem/3190  풀이설명게임이 몇 초에 끝나는 지를 구하는 문제입니다. 규칙은 다음과 같습니다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킵니다. 만약 벽이나 자기 자신의 몸과 부딪히면 게임이 끝납니다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않습니다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워줍니다. 즉, 몸길이는 변하지 않습니다. 뱀의 현재 방향과 몸이 위치한 좌표를 추적해야 합니다.큐를 이용하면 몸이 위치한 좌표를 쉽게 추적할 수 있습니다. 이때는 머리의 위치를 추가로 추적해줘야 합니다. 예시 코드function solution() { const N = Number..

문제벽 부수고 이동하기https://www.acmicpc.net/problem/2206  풀이설명출발점에서 도착점까지 가는 최단 거리를 구하는 문제입니다. 규칙은 다음과 같습니다.상하좌우 인접한 칸으로 이동 가능합니다.벽이 있는 경우, 최대 한 번 부수고 이동할 수 있습니다. BFS를 이용해 해결할 수 있습니다. 거리 배열은 벽을 부순 횟수도 포함해야 하므로 3차원 배열로 만들 수 있습니다. 예시 코드function solution() { const BREAK_LIMIT = 1; const [n, m] = input().split(" ").map(Number); const board = Array.from({ length: n }, () => input().split("").map(Number));..

문제연속합https://www.acmicpc.net/problem/1912  풀이설명n개의 정수로 이루어진 수열에서, 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제입니다. DP를 통해 해결할 수 있습니다. dp[i]는 i번째 수를 마지막으로 포함했을 때 구할 수 있는 최댓값입니다. 정수 배열을 nums라고 할 때,dp[i]의 값은 다음 두 가지 중 더 큰 값입니다.dp[i -1] + nums[i]nums[i] 예시 코드function solution() { const n = Number(input()); const nums = input().split(" ").map(Number); const dp = [nums[0]]; for (let i = 1; i