rlatotquf45 님의 블로그

문제 링크https://www.acmicpc.net/problem/5557문제 요약1학년 상근이는 숫자가 주어졌을 때 마지막 숫자와 등호(=)를 사용하여 올바른 등식을 만들고 싶어 한다. 이때 각 숫자 사이에 덧셈(+) 또는 뺄셈(-) 연산을 넣어 연산을 수행해야 한다. 중간 계산 값은 0 이상 20 이하 범위에 있어야 하며, 이를 벗어나면 올바르지 않은 등식이 된다. 목표는 주어진 숫자 배열을 사용하여 상근이가 만들 수 있는 올바른 등식의 개수를 구하는 것이다.푼 방법DP(동적계획법)으로 풀었습니다. dp[i][j]는 i번째 숫자까지 계산했을 때 j의 값이 나올 수 있는 경우의 수를 의미한다.초기 조건으로 dp[0][nums[0]] = 1로 설정하여 첫 번째 숫자가 나올 수 있는 유일한 경우의 수를 반..

문제 링크https://www.acmicpc.net/problem/31929문제 요약민석이는 앞으로 총 N번의 승리와 M번의 패배를 경험하게 됩니다. 각 승리와 패배는 각각 다른 점수를 주거나 빼앗습니다.승리 시 iii번째 승리에서 Wi만큼의 점수를 얻습니다.패배 시 jjj번째 패배에서 Lj​만큼의 점수를 잃습니다.점수 보호 메커니즘이 존재합니다. 점수는 K점마다 보호 구간이 있으며, 현재 점수가 a×K+b(0)인 상태에서 패배하면 최대 b점까지만 잃습니다. 즉, min⁡(Lj,b)만큼의 점수를 잃습니다. 만약 현재 점수가 a×K라면, 보호 없이 Lj만큼의 점수를 잃습니다.목표는 승리와 패배의 순서를 최적으로 배치하여 N+M번의 게임 후에 최대한 높은 최종 점수를 얻는 것입니다.푼 방법이 문제는 동적 계..

문제 링크https://www.acmicpc.net/problem/16194문제 요약민규는 N개의 카드를 구매하려고 하며, 카드가 iii개 포함된 카드팩의 가격이 P_i일 때, N개의 카드를 구매하기 위해 최소 금액을 구하고자 합니다. 카드팩은 1개에서 N개까지 다양한 크기가 있으며, 카드팩 여러 개를 조합하여 정확히 N개의 카드를 구입해야 합니다.푼 방법 DP 배열 dp[i]: i개의 카드를 구매하는 데 필요한 최소 비용을 저장하는 배열입니다.초기값으로 dp[0]=0을 설정합니다. 이는 카드가 0개 필요할 때 비용이 0원임을 의미합니다.점화식: dp[i]=min⁡(dp[i],dp[i−j]+P[j])카드 i개를 구매할 때, 개 들어 있는 카드팩을 사용하여 i−j개의 카드에서 최소 비용을 계산해 나갑니다...