BOJ
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..
BOJ 16509 · 장군
알고리즘 분류 : BFS 장기 말을 옮기는 최소 횟수를 구하는 문제다. BFS를 통해 상(象)을 옮겨서 왕을 먹어야 한다. 장기판에서 상을 옮겨서 왕의 위치로 도달하는 최소 횟수를 구해야 한다.상은 그림처럼 움직이며, 움직이는 경로에 다른 말이 있으면 해당 위치로 옮길 수 없다. 다른 말은 존재하지 않기 때문에, 왕의 위치가 상의 이동 경로에 있는지만 고려하면 된다.별도로 이동 좌표를 만들고, 움직이는 경로에 왕이 있다면 상을 움직이지 않는다.이동이 가능하다면 옮긴다. C++ 소스코드 #include #include #include using namespace std; struct grid { int x, y; }; int sx, sy, ex, ey; int dist[10][9]; const int dx..