Yepchani's place

[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/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색으로 칠..

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

문제지름길https://www.acmicpc.net/problem/1446  풀이설명운전해야 하는 거리의 최솟값을 구하는 문제입니다. DP를 이용해 해결할 수 있습니다. dp[i]는 i 지점까지 운전해야 하는 거리의 최솟값입니다.dp[0] = 0으로 초기화합니다. 점화식은 다음과 같습니다.고속도로를 따라 이동할 경우dp[i] = Math.min(dp[i], dp[i-1] + 1)지름길로 이동할 경우도착 지점이 end, 길이를 dist라고 할 때dp[end] = Math.min(dp[end], dp[i] + dist) 예시 코드function solution() { const [N, D] = input().split(" ").map(Number); const dp = Array(D + 1).fill(D..

문제2 x n 타일링 2https://www.acmicpc.net/problem/11727   풀이설명직사각형을 채우는 방법의 수를 구하는 문제입니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i칸까지 타일을 채울 수 있는 방법의 수입니다.dp = [0, 1, 3]으로 초기화해줍니다. 타일을 채울 수 있는 방법의 수는 다음과 같습니다.2x1 타일을 놓는 경우, 남은 부분은 2x(n-1)이므로 dp[n-1]가지입니다.1x2 타일을 놓는 경우, 남은 부분은 2x(n-2)이므로 dp[n-2]가지입니다.2x2 타일을 놓는 경우, 남은 부분은 2x(n-2)이므로 dp[n-2]가지입니다. 이를 점화식으로 나타내면 다음과 같습니다.dp[i] = dp[i - 1] + 2 * dp[i - 2] 예시 코드funct..

문제동전https://www.acmicpc.net/problem/9084  풀이설명동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 구하는 문제입니다. DP를 이용해 해결할 수 있습니다. dp[i]는 금액 i를 만들 수 있는 방법의 수입니다.동전 종류와 개수만 가지고 방법을 세므로 누적합을 이용할 수 있습니다.dp[0] = 1로 초기화 해줍니다. 동전 종류가 coin이라고 한다면, i원을 만들 수 있는 방법의 수는 다음과 같습니다.이전까지의 동전 종류로 민들 수 있는 방법의 수 + (i - coin)원을 만들 수 있는 방법의 수입니다.따라서 dp[i] = dp[i] + dp[i - coin]입니다. 예시 코드function solution() { const T = Number(input())..