Yepchani's place

문제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())..

문제주사위 쌓기https://www.acmicpc.net/problem/2116  풀이설명주사위들을 규칙에 따라 쌓아 올렸을 때, 한 옆면의 숫자의 합이 가장 큰 값을 구하는 문제입니다. 주사위에 대한 설명입니다.주사위는 모두 크기가 같은 정육면체이며, 각 면에는 1부터 6까지의 숫자가 적혀있습니다. 그러나 마주 보는 면에 적힌 숫자의 합이 반드시 7인 것은 아닙니다. 주사위를 쌓는 규칙은 다음과 같습니다.아래에서부터 1번, 2번, 3번, ..., N번 주사위 순으로 쌓습니다.서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 합니다.e.g. 1번 주사위의 윗면에 있는 숫자 = 2번 주사위의 아랫면에 있는 숫자각 주사위는 위..

문제도둑질https://school.programmers.co.kr/learn/courses/30/lessons/42897   풀이설명도둑이 훔칠 수 있는 돈의 최댓값을 구하는 문제입니다. dp를 사용해 해결할 수 있습니다. 집이 원형으로 이어지기 때문에 첫 번째 집을 털면 마지막 집을 털 수 없습니다.따라서 dp 배열 2개를 사용해 하나는 첫 번째 집을 털 때를, 다른 하나는 첫 번째 집을 털지 않을 때를 계산합니다. dp[i]는 i번째 집까지 거쳤을 때 훔칠 수 있는 돈의 최댓값입니다. 점화식은 다음과 같습니다.dp[i] = Math.max(dp[i - 2] + money[i], dp[i - 1]) 예시 코드function solution(money) { const n = money.length; ..

문제거스름돈https://school.programmers.co.kr/learn/courses/30/lessons/12907 풀이설명n원을 거슬러 줄 방법의 수를 구하는 문제입니다. dp를 사용해 해결할 수 있습니다. dp[i]는 i원을 거슬러 주는 방법의 수를 의미합니다.dp[0] = 1로 초기화합니다. 각 화폐 단위에 대해서 그 화폐 단위까지 도달하는 방법의 수를 누적해 계산합니다. 점화식은 다음과 같습니다.dp[i] = dp[i] + dp[i - coin] 예시 코드function solution(n, money) { const MOD = 1000000007; const dp = Array(n + 1).fill(0); dp[0] = 1; for (const coin of money) { ..

문제카운트 다운https://school.programmers.co.kr/learn/courses/30/lessons/131129  풀이설명목표 점수가 주어졌을 때, 최선의 경우 던질 다트 수와 그때의 싱글 또는 불을 맞춘 횟수를 구하는 문제입니다. DP로 해결할 수 있습니다. 최선의 경우란, 던질 다트 수를 최소화하고, 다트 수가 같을 경우, 싱글 또는 불을 맞춘 횟수를 최대화한 경우를 말합니다. 다트 하나를 던져서 획득할 수 있는 스코어는 다음과 같습니다.1 ~ 20(1 ~ 20) * 2(1 ~ 20) * 350 dp[i]는 i점을 만들기 위해 필요한 [다트 수, 싱글 또는 불을 맞춘 횟수]입니다.i점은 (i - 스코어)점에 다트 한 개를 추가로 던져 구할 수 있습니다.가능한 스코어를 전부 시도해 보..

문제N으로 표현https://school.programmers.co.kr/learn/courses/30/lessons/42895  풀이설명N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 구하는 문제입니다. dp를 사용해 해결할 수 있습니다. dp[i]는 N을 i번 사용해서 만들 수 있는 수들의 모음입니다.N을 i번 사용해서 만든 수, dp[j]와 dp[i - j]의 조합으로 생성될 수 있습니다. (1  점화식은 다음과 같습니다. 예시 코드function solution(N, number) { const MAX_N_LIMIT = 8; const dp = Array.from({ length: MAX_N_LIMIT + 1 }, () => new Set()); for (let i ..

문제3 x n 타일링https://school.programmers.co.kr/learn/courses/30/lessons/12902  풀이설명길이가 n인 직사각형을 채우는 방법의 수를 구하는 문제입니다. DP를 이용해 해결할 수 있습니다.dp[n]은 길이가 n인 직사각형을 채우는 방법의 수입니다. 직사각형의 길이가 짝수일 때, 각 길이에 맞는 전용 블록을 만들 수 있습니다. 만들 수 있는 전용 블록의 종류는 다음과 같습니다.n = 2일 때, 3가지n = 4 이상의 짝수일 때, 2가지 아래는 그 예시입니다. 따라서 dp[n] = dp[n - 2]에 길이가 2인 전용 블록을 채우는 가짓수 + dp[n - x]에 길이가 x인 전용 블록을 채우는 가짓수입니다. (x는 4이상의 짝수) 단, dp[0]은 아무것도..