알고리즘
BOJ 16194 · 카드 구매하기 2
알고리즘 분류 : 다이나믹 프로그래밍 DP를 통해 카드를 구매하기 위해 지불하는 금액의 최솟값을 구해야 한다. BOJ 11052번 '카드 구매하기'에서 최댓값 대신 최솟값을 구하면 된다. D[N] : 카드 N장을 구입하기 위한, 지불 금액의 최솟값D[0] = 0, D[1] = P[1]D[N-1] + P[1] : 카드 1개 들어있는 카드팩을 구매하고, 카드 N-1장을 구매한 지불 금액의 최솟값D[N-2] + P[2]‥‥D[0] + P[N] : 카드 N개 들어있는 카드팩을 구매하고, 카드 0장을 구매한 지불 금액의 최솟값 C++ 소스코드 #include #include using namespace std; int n, d[1001], p[1001]; void solve() { d[0] = 0, d[1] = ..
BOJ 11052 · 카드 구매하기
알고리즘 분류 : 다이나믹 프로그래밍 DP를 통해 카드를 구매하기 위해 지불하는 금액의 최댓값을 구해야 한다. D[N] : 카드 N장을 구입하기 위한, 지불 금액의 최댓값D[0] = 0, D[1] = P[1]D[N-1] + P[1] : 카드 1개 들어있는 카드팩을 구매하고, 카드 N-1장을 구매한 지불 금액의 최댓값D[N-2] + P[2]‥‥D[0] + P[N] : 카드 N개 들어있는 카드팩을 구매하고, 카드 0장을 구매한 지불 금액의 최댓값 C++ 소스코드 #include #include using namespace std; int n, d[1001], p[1001]; void solve() { d[0] = 0, d[1] = p[1]; for (int i=2; i
BOJ 10844 · 쉬운 계단 수
알고리즘 분류 : 다이나믹 프로그래밍 DP를 통해 계단 수의 총개수를 구하는 문제다. D[N][M] : M으로 끝나는 N자리 계단 수의 총개수D[1][1] = 1, D[1][2] = 1, ‥‥ , D[1][9] = 1 (한 자릿수)D[N][0] = D[N-1][1] : 0으로 끝나는 N자리 계단 수의 총개수D[N][1] = D[N-1][0] + D[N-1][2] : 1로 끝나는 N자리 계단 수의 총개수‥‥D[N][8] = D[N-1][7] + D[N-1][9]D[N][9] = D[N-1][8] C++ 소스코드 #include const int mod = 1000000000; int n; long long ans, d[101][10]; void solve() { for (int i=1; i 0: d[i][..
BOJ 15988 · 1, 2, 3 더하기 3
알고리즘 분류 : 다이나믹 프로그래밍 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 한다. BOJ 9095번 '1, 2, 3 더하기'에서 범위가 확장된 문제다. D[N] : 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수D[1] = 1D[2] = 2 (1+1, 2)D[3] = 4 (1+1+1, 1+2, 2+1, 3)D[N-1] : 마지막에 1을 더한 방법의 수D[N-2] : 마지막에 2를 더한 방법의 수D[N-3] : 마지막에 3을 더한 방법의 수 C++ 소스코드 #include int n; long long d[1000001]; void solve() { d[1] = 1, d[2] = 2, d[3] = 4; for (int i=4; i
BOJ 9095 · 1, 2, 3 더하기
알고리즘 분류 : 다이나믹 프로그래밍 기초적인 DP 문제이다. 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 한다. D[N] : 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수D[1] = 1D[2] = 2 (1+1, 2)D[3] = 4 (1+1+1, 1+2, 2+1, 3)D[N-1] : 마지막에 1을 더한 방법의 수D[N-2] : 마지막에 2를 더한 방법의 수D[N-3] : 마지막에 3을 더한 방법의 수 C++ 소스코드 #include int n, d[11]; void solve() { d[1] = 1, d[2] = 2, d[3] = 4; for (int i=4; i
BOJ 11727 · 2×n 타일링 2
알고리즘 분류 : 다이나믹 프로그래밍 기초적인 DP 문제이다. BOJ 11726번 '2×n 타일링'에서 살짝 변경해주면 된다.D[N] : 2xN 사이즈의 직사각형을 2x2, 2x1 사각형으로 채우는 방법의 수D[0] = D[1] = 1D[N-1] : 마지막 조각을 2x1 사각형으로 채운 방법의 수D[N-2] : 마지막 조각을 2x2 사각형 또는 2x1 사각형 2개로 채운 방법의 수 C++ 소스코드 #include int d[1001]; int solve(int n) { d[0] = d[1] = 1; for (int i=2; i
BOJ 11726 · 2×n 타일링
알고리즘 분류 : 다이나믹 프로그래밍 기초적인 DP 문제이다. 그림 이해를 통해 점화식을 만들고 구현하면 된다.D[N] : 2xN 사이즈의 직사각형을 1x2, 2x1 사각형으로 채우는 방법의 수D[0] = D[1] = 1D[N-1] : 마지막 조각을 2x1 사각형으로 채운 방법의 수D[N-2] : 마지막 조각을 1x2 사각형 2개로 채운 방법의 수 C++ 소스코드 #include int d[1001]; int solve(int n) { d[0] = d[1] = 1; for (int i=2; i
BOJ 1463 · 1로 만들기
알고리즘 분류 : 다이나믹 프로그래밍 기초적인 DP문제이다. 3가지 조건을 따져서 점화식을 만들고, 이를 구현하면 된다. D[N] : N을 1로 만드는 최소 연산 횟수D[1] = 0D[N-1] + 1 : N에서 1을 뺀 경우D[N/3] + 1 : N을 3으로 나눈 경우D[N/2] + 1 : N을 2로 나눈 경우 C++ 소스코드 #include int d[1000001]; int solve(int n) { d[1] = 0; for (int i=2; i temp) d[i] = temp; } if (i%2 ==0) { int temp = d[i/2]+1; if (d[i] > temp) d[i] = temp; } } return d[n]; } int main() { int n; scanf("%d", &n); p..