본문 바로가기

Algorithm/Dynamic Programming

 (32)
[C++] 백준 15988번 : 1, 2, 3 더하기 3 (S2) #문제 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 int 범위의 최대는 2,147,483,647이다. 대략 2,000,000,000으로 기억해두자. 문제에서 dp배열을 int로 선언하면, dp[i - 1] + dp[i - 2] + dp[i - 3]을 계산할 때, int범위의 최댓값을 벗어날 수 있다. 따라서 dp배열을 long long으로 선언해야 한다. 모듈로 연산의 성질인 (A + B)%C = (A%C + B%C)%C도 기억해두자. 이때, (A%C + B)%C도 가능하다는 점도..
[C++] 백준 9095번 : 1, 2, 3 더하기 (S3) #문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 마지막에 올 수 있는 수는 1,2,3 중 하나이다. 그리고 마지막 수를 빼면 같은 문제로 문제의 크기만 n-1, n-2, n-3이 되므로 dp를 이용한다. 이때 dp배열의 초깃값으로 dp[1]=1, dp[2]=2, dp[3]=4를 넣어주고 반복문으로 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]을 통해 dp[10]까지 계산한다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #inclu..
[C++] 백준 11727번 : 2×n 타일링 2(S3) #문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net #풀이 & 학습한 내용 기존 2×n 타일링 문제에서 마지막에 올 수 있는 경우가 하나 추가된 문제이다. 타일의 마지막은 2x1타일 하나, 1X2타일 2개, 2X2타일 1개가 가능하다. 각각에 따른 문제는 같은 문제로 사이즈만 n-1, n-2, n-2일때와 같다. dp배열의 초기값으로 n=1일 때 1, n=2일 때 3을 넣어줬다. 그리고 dp[i] = (dp[i - 1] + 2 * dp[i - 2])를 통해 for문으로 순차적으로 dp..
[C++] 백준 11726번 : 2×n 타일링 (S3) #문제 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net #풀이 & 학습한 내용 마지막에 타일이 올수 있는 경우는 1개가 서있는것과, 2개가 가로로 누워있는 것이다. 각각의 경우는 n-1과 n-2일 때의 문제를 푸는 것과 동일하므로 dp를 이용하여 앞에서부터 순차적으로 n까지 dp배열을 채워나간다. 이때 dp의 basis case는 n=1일 때 1과 n=2일 때 2이다. 또한, 문제에서 무언가로 나눈 답을 구하란 것을 문제를 푸는 과정에서 나누면서 구하라는 뜻이다. #소스코드 1 ..
[C++] 백준 1463번 : 1로 만들기 (S3) #문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net #풀이 & 학습한 내용 우선 최솟값을 구할 때 #include 의 min에 {}로 대소 비교할 값들을 묶어서 전달하여 최솟값을 구했다. 또한, dp를 이용할 때 먼저 basis case로 숫자가 2와 3일 때의 dp배열에 1 값을 넣었으며, 이후에는 for문을 통해 N까지 순차적으로 계산하였다. 이때, 경우는 2와 3으로 모두 나누어 떨어질 때, 2로만 나누어 떨어질 때, 3으로만 나누어 떨어질 때, 2와 3 모두로 나누어 떨어지지 않을 때로 나누었다. 연산의 횟수이므로 이전의 optimization에 1을 더해주어 ..
[C++] 백준 11048번 : 이동하기 (S1) #문제 www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net #풀이 & 학습한 내용 opti[i][j]를 (i,j)위치까지 얻을 수 있는 최대 candy수로 두고, bottom up방식을 통해 table을 하나씩 채워나간다. 이때, opti[i][j]에서 필요한 정보는 왼쪽과 위쪽 정보이기 때문에 이를 고려하여 for문을 구성한다. 나는 테이블에 넣는 basis를 아래로만 가는 경우, 오른쪽으로만 가는 경우에 대해서 채워주고 table의 다른 ..
[C++] 백준 11049번 : 행렬 곱셈 순서 (G3) #문제 www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net #풀이 & 학습한 내용 행렬 사이의 곱셈에 순서대로 숫자를 부여한 뒤에, M[i][j]가 Ai부터 Aj까지의 곱에서의 최소 곱셈수를 의미하도록 했다. M[i][j]를 마지막 곱셈이 이루어진 곳을 의미하는 k가 i부터 j-1까지 값을 가질때, (M[i][k] + M[k+1][j]+ 마지막곱셈에서의 곱셈수)중 최소 값을 갖게 Optimal substructure를 구현했다. dp의 주요 개념인..
[C++] 백준 2839번 : 설탕 배달 (B1) #문제 www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그�� www.acmicpc.net #풀이 이 문제는 dp를 통해 해결하는 문제이다. Nkg 최적화 문제를 N-3kg 최적화 문제와 N-5kg 최적화 문제를 통해 답을 도출하는 optimal substructure로 구현했다. 기본적인 구현은 쉬웠지만, 정확하게 N킬로그램을 만들 수 없을 때 -1을 출력하게 만드는 것에서 약간 고민을 해야했다. 문제를 해결한 뒤 다른 분의 dp풀이(링크) 코드를 봤는데, 훨씬 깔끔했다. 나는 3을 빼고 5를 빼는..

티스토리툴바