Yepchani's place

문제1로 만들기 2https://www.acmicpc.net/problem/12852  풀이설명정수 X를 1로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음과 같습니다.X가 3으로 나누어 떨어지면, 3으로 나눕니다.X가 2로 나누어 떨어지면, 2로 나눕니다.1을 뺍니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i를 만드는 데 필요한 연산의 최소 횟수입니다. 점화식은 다음과 같습니다.dp[i]는 다음 세 가지 값 중 최솟값입니다.dp[i - 1] + 1i가 2로 나누어 떨어지는 경우, dp[i / 2] + 1i가 3으로 나누어 떨어지는 경우, dp[i / 3] + 1 추가적으로 경로 배열을 하나 만들어, dp 값이 업데이트 될 때마다 경로를 저장합니다.dp..

문제격자상의 경로https://www.acmicpc.net/problem/10164  풀이설명조건을 만족하는 서로 다른 경로의 수를 구하는 문제입니다. 조건은 다음과 같습니다.로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있습니다. (즉, 대각선 방향으로는 이동할 수 없습니다.) 격자에 O로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 합니다.1번 칸과 N × M번 칸은 O 표시가 되어 있지 않습니다.O 표시가 되어 있는 칸은 최대 한 개입니다. DP를 사용해 해결할 수 있습니다. O 표시가 된 칸을 K라고 할 때, 격자에서 갈 수 있는 영역은 K의 우상단과 K의 좌하단입니다.따라서 해당 부분에 대한 경로만 구하면 됩니다. 예시 코드function solution..

문제1로 만들기https://www.acmicpc.net/problem/1463  풀이설명정수 X를 1로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음과 같습니다.X가 3으로 나누어 떨어지면, 3으로 나눕니다. X가 2로 나누어 떨어지면, 2로 나눕니다. 1을 뺍니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i를 만드는 데 필요한 연산의 최소 횟수입니다. 점화식은 다음과 같습니다.dp[i]는 다음 세 가지 값 중 최솟값입니다.dp[i - 1] + 1i가 2로 나누어 떨어지는 경우, dp[i / 2] + 1i가 3으로 나누어 떨어지는 경우, dp[i / 3] + 1 예시 코드function solution() { const N = +input(); co..

문제욕심쟁이 판다https://www.acmicpc.net/problem/1937  풀이설명판다가 이동할 수 있는 칸의 수의 최댓값을 구하는 문제입니다. 규칙은 다음과  같습니다.판다의 초기 위치는 어떤 칸이든 될 수 있습니다.상, 하, 좌, 우로 인접한 칸 중 하나로 이동합니다.새로 이동하는 칸은 이전 칸보다 대나무가 많아야 합니다. 그래프 탐색과 DP를 이용해 해결할 수 있습니다. dp[x][y]는 (x, y)에서 시작했을 때, 이동할 수 있는 칸의 수의 최댓값입니다. 다음 칸의 위치를 (nx, ny)라고 할 때, 점화식은 다음과 같습니다.dp[x][y]는 다음 두 값 중 최댓값입니다.dp[x][y]dp[nx][ny] + 1 모든 칸에서 그래프 탐색을 진행하고, 각 칸에 대한 dp 값을 업데이트합니다..

문제구간 합 구하기 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/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

문제계단 오르기https://www.acmicpc.net/problem/2579  풀이설명계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 문제입니다. 규칙은 다음과 같습니다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있습니다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다다음 계단으로 오를 수 있습니다.연속된 세 개의 계단을 모두 밟아서는 안 됩니다. 단, 시작점은 계단에 포함되지 않습니다.마지막 도착 계단은 반드시 밟아야 합니다. DP를 통해 해결할 수 있습니다. dp[i]는 i번째 계단까지 밟았을 때 얻을 수 있는 최대 점수입니다. 계단에 써있는 점수를 담은 배열을 stairs라고 할 때,dp[i]의 값은 다음 두 가지 중 더 큰 값입니다.dp[i - 2] + stairs..

문제RGB거리 2https://www.acmicpc.net/problem/17404  풀이설명모든 집을 칠하는 비용의 최솟값을 구하는 문제입니다.규칙은 다음과 같습니다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 합니다. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 합니다. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 합니다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 합니다. RGB거리 문제에서 규칙만 조금 바뀌었습니다. 첫 번째 집에서 고른 색은 마지막 집에서 고를 수 없습니다.DP를 이용해 해결할 수 있습니다. dp[i][j]는 i번째 집까지 색칠을 마쳤고, i번째 집을 j색으로 칠했을 때의 비용의 최솟값입니다. i번째 집을 j색으로 칠..